无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1：
输入：s = "abcabcbb"
输出：3
解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。
示例 2：
输入：s = "bbbbb"
输出：1
解释：因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3：
输入：s = "pwwkew"
输出：3
解释：因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 10^5s由英文字母、数字、符号和空格组成
滑动窗口-哈希表：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> last;
int left = 0;
int ans = 0;
for (int right = 0; right < s.size(); right++)
{
char c = s[right];
if (last.count(c) && last[c] >= left)
{
left = last[c] + 1;
}
last[c] = right;
ans = max(ans, right - left + 1);
}
return ans;
}
};
核心思想
这题要求的是 子串，不是子序列。
子串必须是原字符串中连续的一段，所以我们可以用一个窗口 [left, right] 表示当前正在考虑的连续区间。
我们希望这个窗口始终满足：
窗口内部没有重复字符。
然后不断移动右边界 right，把新的字符加入窗口。
如果加入后没有重复字符，说明当前窗口仍然合法，可以更新答案。
如果加入后出现重复字符，就需要移动左边界 left，直到窗口重新变成无重复字符。
这里的关键是：
不需要一步一步移动
left，可以直接跳到重复字符上一次出现位置的后一位。
所以代码里用 last 记录每个字符上一次出现的位置。
为什么要用哈希表记录上一次出现位置
假设当前遍历到下标 right，字符是：
s[right] = c
如果字符 c 之前没有出现过，那么直接加入窗口即可。
如果字符 c 之前出现过，设它上一次出现的位置是：
last[c]
这时还要分两种情况。
1. last[c] < left
说明这个重复字符出现在当前窗口左边，已经不在窗口里了。
当前窗口 [left, right] 中并没有重复的 c，所以不需要移动 left。
例如：
s = "abba"
当遍历到最后一个 'a' 时，前一个 'a' 在下标 0。
如果此时窗口左边界已经移动到了 2，那么下标 0 的 'a' 已经不在窗口里，不会造成重复。
2. last[c] >= left
说明字符 c 上一次出现的位置还在当前窗口里。
此时如果继续保留原来的 left，窗口中就会有两个 c：
- 一个在
last[c] - 一个在
right
所以为了让窗口重新合法，必须把 left 移动到：
last[c] + 1
这样才能把前一个 c 排除出窗口。
代码就是：
left = last[c] + 1;
然后更新：
last[c] = right;
表示字符 c 最近一次出现的位置变成了当前下标。
公式推导
当前窗口是：
[left, right]
如果这个窗口没有重复字符，那么它的长度是：
right - left + 1
所以每次处理完 right 以后，都可以用这个长度更新答案：
ans = max(ans, right - left + 1);
为什么这个长度一定可以参与更新？
因为在更新答案之前，代码已经处理过重复字符：
- 如果
s[right]没有在窗口中出现过，窗口本来就是合法的 - 如果
s[right]在窗口中出现过，left已经移动到上一次出现位置的后一位
因此此时 [left, right] 一定是一个无重复字符的子串。
为什么 left 不能往回走
代码里移动左边界时，有一个很重要的判断：
if (last.count(c) && last[c] >= left)
只有当上一次出现的位置在当前窗口内，才更新 left。
不能直接写成：
left = last[c] + 1;
因为这样可能会让 left 往回走，导致已经排除掉的重复字符又回到窗口中。
仍然用：
s = "abba"
来说明。
遍历过程：
right = 0，窗口"a"，left = 0right = 1，窗口"ab"，left = 0right = 2，遇到重复'b'，left移到2，窗口"b"right = 3，遇到'a'
此时 'a' 上一次出现的位置是 0。
如果直接令：
left = 0 + 1 = 1
窗口就会变成：
"bba"
里面有两个 'b'，反而变成非法窗口。
所以只有当：
last[c] >= left
也就是上一次出现位置仍然在当前窗口中时，才需要移动 left。
正确性证明
我们证明：算法返回的 ans 等于字符串中无重复字符最长子串的长度。
归纳不变式
在每次循环处理完下标 right 后，窗口 [left, right] 满足：
- 窗口内没有重复字符。
- 在所有以
right结尾的无重复子串中，[left, right]的左端点最靠左，也就是长度最长。
归纳基
当 right = 0 时，窗口中只有一个字符。
单个字符一定没有重复，所以窗口合法。
同时，以 0 结尾的子串只有它自己，因此它也是最长的。
归纳不变式成立。
归纳假设
假设处理完 right - 1 时，窗口 [left, right - 1] 已经满足上面的两个条件。
归纳推导
现在处理 s[right]。
如果 s[right] 没有在当前窗口中出现过，那么把它加入窗口后，窗口仍然没有重复字符。
并且由于原来的 left 已经是以 right - 1 结尾时能取到的最靠左位置，加入一个不重复的新字符后，left 仍然不需要右移。
所以 [left, right] 是以 right 结尾的最长无重复子串。
如果 s[right] 在当前窗口中出现过，设上一次出现位置为 last[s[right]]。
为了让以 right 结尾的子串没有重复字符，左端点必须满足：
left > last[s[right]]
否则窗口中会同时包含两个 s[right]。
因此新的左端点最小只能是：
last[s[right]] + 1
代码正是把 left 更新为这个位置。
这样得到的窗口 [left, right]：
- 排除了前一个重复字符
- 保留了尽可能多的左侧字符
所以它仍然是以 right 结尾的最长无重复子串。
归纳不变式继续成立。
得出结论
每次循环结束后，[left, right] 都是以 right 结尾的最长无重复子串。
算法用：
ans = max(ans, right - left + 1);
枚举了每一个右端点对应的最优答案。
而任意一个子串都有自己的右端点，所以全局最长无重复子串一定会在某一次更新中被统计到。
因此最终返回的 ans 正确。
复杂度分析
right 从左到右遍历字符串一次。
left 也只会向右移动，不会向左移动。
所以总时间复杂度为：
O(n)
其中 n 是字符串长度。
哈希表最多记录字符串中出现过的字符，因此空间复杂度为：
O(|Σ|)
其中 |Σ| 表示字符集大小。
如果只考虑题目中的英文字母、数字、符号和空格，也可以看作常数空间。