题目链接：3.无重复字符的最长子串

题解：

双指针形成的滑动窗口实现！双指针被形象表示为滑动窗口！

题目简述：

两个概念：

  1. 子串：连续的
  2. 子序列：不一定连续，下标递增

找出一个字符串中最长不重复的子串，返回最大长度！

题解：

使用两个指针i, j，（j < i）, 区间[j, i]表示以 i 为尾的子串的区间。

使用 unordered_map<char, int> hash来表示 字符出现的次数。

双指针扫描时来维护该区间[j, i]，使得该区间为以 i 为底的，保证不重复的最大区间。

  1. 初始[j, i]无重复，i往后走，将其加入哈希表
  2. 若加入后，hash[s[i]] > 1说明 i位置出现了和前面重复的字符，由于前面是不重复的，所以只有可能是i位置的字符重复，接下来，j开始后移，同时进行hash[s[j++]]--来j将哈希表前面的字符清零，直到找到一个新的 j使的 hash[s[i]] > 1不成立，即当前 j 的位置为与 i重复字符的下一个字符，当前[j, i]为以 i为尾的最长子串。

画一个简图如下：

时间复杂度：每个点最多被i 和 j 各扫描一次，所以为 O(N)

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        // 字符出现的个数
        unordered_map<char, int> hash;
        // [j, i]
        for(int i = 0, j = 0; i < s.size(); i++){
            hash[s[i]]++;
            while(hash[s[i]] > 1){
                hash[s[j++]]--;
            }
            res = max(res, i - j + 1);
        }
        return res;
    }
};