(力扣) 3. 无重复字符的最长子串

发表于 更新于 分类于 ，

题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

解题思路

定义 startstart 和 nownow 指针，然后遍历 s 的每一个字符，若该字符不在 substrsubstr 集合里，则插入，否则计数变量 numnum 归零，startstart 指针指向下一个点，清除 substrsubstr 集合并且将 nownow 指针移动回 startstart，知道 nownow 移动到最后。

代码实现

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
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int now = 0;
        int start = 0;
        int num = 0;
        int maxNum = 0;
        unordered_set<char> substr;
        while(now != s.length())
        {
            if(substr.count(s[now]) == 0)
            {
                substr.insert(s[now]);
                num ++;
                now++;
                if(num > maxNum)
                {
                    maxNum = num;
                }
            }
            else
            {
                num = 0;
                start ++;
                now = start;
                substr.clear();
            }
        }
        return maxNum;
    }
};

高级版

该解法来源于题目评论区

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> m(128, 0);//这个容器为了存当遇到相同的字符(假设是a)时i应该变成的值，即前面那个a的下一个字符
        int ans = 0;//最终的子串长度
        int i = 0;
        for (int j = 0; j < s.size(); j++)
        {
            i = max(i, m[s[j]]);//如果遇到了相同的字符(假设为a)，此时m[s[j]]会又去到同样的存储单元m[a的ASCII码值]，因为之前遇到a时已经将这个位置的值改成前面那个a的下一个位置了，所以m[s[j]]大于i，将i更新
            m[s[j]] = j + 1;//更新这个位置的值，当下次再遇到该字母时，将i调整到该字母下一个位置的地方
            ans = max(ans, j - i + 1);//更新最终结果值，即没相同字母的子串的字符个数
        }
        return ans;
    }
};