Longest Substring Without Repeating Characters

发表于 | 分类于

Longest Substring Without Repeating Characters

题目描述：

给定一个字符串，找到字符串中最长的子串的长度，其子串中的所有字母不重复。见LeetCode3

例子：

‘abcabcbb’其中最长的不重复子串的长度是3；’abba’其中最长的不重复的子串的长度是2。

解题思路：

我们在遍历字符串的过程中，每遍历一个新的位置需要知道当前位置的字母是否曾经在前面中出现，因此我们需要一个哈希表来记录我们先前遍历字母和字母所在的位置；其次在遇到与先前的字母重复时，我们需要找到最靠右侧的那个位置；所以我们需要在哈希表中保存着这个字母在字符串中最右侧的位置。综上整体的思路是，我们定义start和end来代表当前子串的头和尾；用哈希表来保存先前遍历过程中所遇到的字母和字母所在的最右的位置；遍历过程中，如果是不重复的字母，则需要end++并更新当前的最长子串长度；如果是重复的，需要判断该字母出现的位置在start的左侧还是右侧，如果是左侧则不影响当前子串；如果是右侧需要更新start到该位置的下一个地方；然后更新子串的长度。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 0)
            return 0;// 字符串为空的情况
            
        int length = 1;
        int start = 0;
        int end = 0;
        map<char, int> hash; //定义所需要的变量
        while(start < s.size() && end < s.size()){
            if (hash.find(s[end]) == hash.end()){
                hash.insert({s[end], end});
                // 如果不存在，更新哈希表
                length = max(end - start + 1, length);
                //更新长度
                end++;
                //遍历下一个字母
            }else{
                if (start < hash[s[end]] + 1)
                    start = hash[s[end]] + 1;
                 // 判断该位置在start的左侧或者右侧决定是否更新
                hash[s[end]] = end;
                // 更新该字母到最右侧的位置
                length = max(end - start + 1, length);
                end++;
                // 更新长度和继续遍历下一个位置
            }
        }
        return length;
        
    }
};