【力扣】无重复字符的最长子串，滑动窗口 + 哈希集合

���重复字符的最长子串原题地址

方法一：滑动窗口（双指针） + 哈希集合

考虑找出字符串s的所有的无重复字符的子串，求出这些子串长度的最大值即可。

使用下标 [left,right] 来维护子串。我们只需要找到每一个 left 对应的所有 right 即可，换句话说，固定了 left 之后，我们让 right 从 left 的位置开始，向后滑动，直到 [left,right] 出现重复字符为止。

以下为所有无重复字符的子串：

(a) b c a b c b b(a b) c a b c b b(a b c) a b c b ba (b) c a b c b ba (b c) a b c b ba (b c a) b c b ba b (c) a b c b ba b (c a) b c b ba b (c a b) c b ba b c (a) b c b ba b c (a b) c b ba b c (a b c) b ba b c a (b) c b ba b c a (b c) b ba b c a b (c) b ba b c a b (c b) ba b c a b c (b) ba b c a b c b (b)

由于我们要找的是这些子串中最长的那个，所以固定 left 后，先让 right 右移至出现重复字符或者 right 移动到字符串的末尾，再统计该子串的长度，即 right-left+1 ，求出其中的最大值即可。

需要统计如下子串的长度：

(a b c) a b c b ba (b c a) b c b ba b (c a b) c b ba b c (a b c) b ba b c a (b c) b ba b c a b (c b) ba b c a b c (b) ba b c a b c b (b)

显然，当某条子串 [left,right] 的右端点 right 已经到达字符串的末尾时，若 left 继续右移，只会缩短子串长度，所以此时无需继续统计。

为了判断子串是否已经出现重复字符，可以利用哈希集合（如 C++ 中的 unordered_set ），来存储 [left,right] 中的所有字符，当 right 右移时，就把最右边的字符添加到哈希集合中；当 left 右移时，就把最左边的字符从哈希集合中删除。这样，每次只需判断子串新增加的字符是否已经在哈希集合中出现过即可。

// 方法一：滑动窗口class Solution{public:    int lengthOfLongestSubstring(string s)    {        if (s.empty())        {            return 0;        }        unordered_set us;        int ans = 0;        // [left,right] 表示子串        int left = 0, right = 0;        us.insert(s[0]);        while (1)        {            // 右指针右移，直到出现重复字符            while (right + 1  
方法二：对方法一的优化，实现左指针 left 的快速跳转
 
方法一是固定 left ，让 right 尽可能右移，从而统计所有的 [left,right] 区间长度 right-left+1 的最大值，这样最坏情况下 left 会遍历完整个字符串。
 
考虑用 key-value 模型的哈希表（如 C++ 中的 unordered_set ），每次把 [0,right] 的字符及其对应下标都存进去。
 
我们用 right 遍历字符串，若 right 右移后指向的字符在哈希表中出现过，且最后出现的下标在 [left,right] 的范围内，说明此时的子串 [left,right] 已经出现了重复字符，此时 left 应该跳转到 s[right] 最后一次出现的位置的后面。
 
下面的例子中， right 本来指向 f ，右移后指向 c ， left 就要从 a 直接跳转到第一个 c 后面，否则 [left,right] 会出现重复字符。
 
(a b c d e f) ca b c (d e f c)
 
每次 right 右移后，都要把 s[right] 及对应的下标 right 都存储到哈希表中，也就是把 s[right] 当前最后出现的位置存储到哈希表中。
 
// 方法二：滑动窗口优化class Solution{public:    int lengthOfLongestSubstring(string s)    {        if (s.size() second + 1);            }            // 子串长度为 right-left+1            ans = max(ans, right - left + 1);            um[s[right]] = right;        }        return ans;    }};