无重复字符的最长子串
一、问题描述
- 难度：中等
- 标签：哈希表、字符串、滑动窗口
给定一个字符串
s，请你找出其中不含有重复字符的最长子串的长度。
你可能见过一个类似的益智题：在下方的矩阵中找出 8
B B B B B B B B B B B B B B
B B B B B B B B B B B B B B
B B B B B B B B B B B B B B
B B B B B B B B B B B B B B
B B B B B B B B B B B B B B
B B B B B B B B B B B B B B
B B B B B B B B B B B 8 B B
B B B B B B B B B B B B B B
你会怎么找呢？
第一种方法，你通过检查每一个横排或者每一个竖列，找到 8，这是大多数人可以想到的思路，操作起来也比较简单。
第二种方法，把视野缩小，用纸挡住一部分，迫使你自己只能看到一小部分，少了干扰自然也就好找了。
这两个方法其实看上去差不多，都是尽可能集中注意力。但是第一种方法的效率远低于第二种方法。在后文中，第一种方法称为暴力循环，第二种方法称为滑动窗口。
二、示例
案例一
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
案例二
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
案例三
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
三、提示
- 0 <= s.length <= 5 * 10^4
- s 由英文字母、数字、符号和空格组成
四、解题
方法一：暴力循环
思路
最直观的想法是枚举所有可能的子串，检查每个子串是否包含重复字符，记录最长的无重复子串长度。
实现
- 使用两层循环枚举所有子串的起始和结束位置
- 对每个子串，使用集合或数组检查是否有重复字符
- 更新最大长度
class Solution(object):def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""n = len(s)max_len = 0for i in range(n):seen = set()for j in range(i, n):# 如果当前字符已存在，跳出内层循环if s[j] in seen:breakseen.add(s[j])max_len = max(max_len, j - i + 1)return max_len
C++ 示例
class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.length();int maxLen = 0;// 枚举所有子串for (int i = 0; i < n; i++) {unordered_set<char> seen;for (int j = i; j < n; j++) {// 如果当前字符已存在，跳出内层循环if (seen.count(s[j])) {break;}seen.insert(s[j]);maxLen = max(maxLen, j - i + 1);}}return maxLen;}
};
时间复杂度： \(O(n^3)\) 两层循环 + 集合操作
空间复杂度： \(O(min(m,n))\) m 是字符集大小
可以发现，两层循环会有重复比较，是否可以优化呢？我们可以使用前文提到的滑动窗口。
方法二：滑动窗口
滑动窗口的基本思路就是使用窗口，左侧的边界和右侧的边界内是最长的不重复字符串长度，右侧不断加入新的字符，如果新加入的字符与左侧的某个字符重复，那么就把左侧的边界向右移动，直到不重复为止。
移动的过程中，保留最长的字符串长度。
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_set<char> window;int maxLen = 0;int left = 0, right = 0;while (right < s.length()) {// 扩展右边界，直到遇到重复字符while (right < s.length() && window.find(s[right]) == window.end()) {window.insert(s[right]);right++;}// 更新最大长度maxLen = max(maxLen, right - left);// 收缩左边界，直到移除重复字符if (right < s.length()) {while (left < right && s[left] != s[right]) {window.erase(s[left]);left++;}window.erase(s[left]);left++;}}return maxLen;}
};
是否还可以优化呢？
想一下，我们移动左侧的边界是为了不重复，比如 abcbdefgh，第二次出现 b 字符的时候，意味着前面一定出现过 b，我们是不是可以直接跳到首次出现 b 后面一个位置呢？
还是以 abcbdefgh 为例，可以在第二次出现 b 的时候，直接跳到滑动窗口中第一个 b 的后面一个位置，这样不就保证了后面的字符不重复了吗！
有可能出现意外的情况吗？比如跳转的时候，在前面的序列中有最长字串，但是跳过的时候，忽略了，导致不完全。
我们来证明一下：
假设我们在位置 j 发现了重复字符，需要跳转到位置 k+1（其中 k 是该字符在当前窗口中的首次出现位置）。
对于任何被跳过的区间 [i, k]（其中 i 是当前左边界），以 i' （i ≤ i' ≤ k） 为起点的子串都必然包含重复字符，因为：
子串 [i', j] 必然包含位置 k 和位置 j 的字符，这两个位置的字符相同，所以任何包含这两个位置的子串都是存在重复的。
换句话说：任何包含重复字符的子串都不可能是最优解，所以可以安全地跳过它们。
方法三：滑动窗口 + 哈希表（推荐解法）
思路
使用滑动窗口，往右侧移动，维护一个无重复字符的窗口。当遇到重复字符时，更改左侧的索引为左侧重复字符的下一个字符。
每次移动都记录字符序列的数量，比较上一次和当前的值大小，返回最大值。
步骤
- 使用两个指针 left 和 right 表示滑动窗口的边界
- 使用哈希表记录每个字符最近出现的位置
- 右指针逐步扩展窗口，当遇到重复字符时，移动左指针
- 实时更新最大窗口长度
这里看不懂没关系，后面还会解释
class Solution:def lengthOfLongestSubstring(self, s: str) -> int:char_sequence = {} # 字符序列max_len = 0left = 0 # 滑动窗口左边界for right, char in enumerate(s): # right 滑动窗口右边界，char 字符# 如果字符在窗口内已出现过，则收缩左边界# 并且忽略已经被甩出窗口的历史记录，只把真正落在当前窗口内的重复字符当作冲突来处理。if char in char_sequence and char_sequence[char] >= left:left = char_sequence[char] + 1# 更新字符最新位置char_sequence[char] = right# 更新最大长度max_len = max(max_len, right - left + 1)return max_len
C++ 代码示例
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char, int> charIndex; // 字符 -> 最近出现的索引int maxLen = 0;int left = 0; // 滑动窗口左边界for (int right = 0; right < s.length(); right++) {char currentChar = s[right];// 如果当前字符在窗口内已存在，移动左指针if (charIndex.find(currentChar) != charIndex.end() &&charIndex[currentChar] >= left) {left = charIndex[currentChar] + 1;}// 更新字符最新位置charIndex[currentChar] = right;// 更新最大长度maxLen = max(maxLen, right - left + 1);}return maxLen;}
};
需要注意的是，这里比较的是 right 和 left，每次变化只是记录最近一次字符出现的位置，而不是删除左侧的重复字符。
以 abcabcbb 来说
| right | char | char 序列 | left | 当前窗口 | 最大长度 |
|---|---|---|---|---|---|
| 0 | 'a' | {'a':0} |
0 | "a" | 1 |
| 1 | 'b' | {'a':0, 'b':1} |
0 | "ab" | 2 |
| 2 | 'c' | {'a':0, 'b':1, 'c':2} |
0 | "abc" | 3 |
| 3 | 'a' | 'a' 在窗口内（0 ≥ 0），移动左侧边界 → left = 1 |
1 | "bca" | 3 |
| 4 | 'b' | 'b' 在窗口内（1 ≥ 1），移动左侧边界 → left = 2 |
2 | "cab" | 3 |
| 5 | 'c' | 'c' 在窗口内（2 ≥ 2），移动左侧边界 → left = 3 |
3 | "abc" | 3 |
| 6 | 'b' | 'b' 在窗口内（4 ≥ 3），移动左侧边界 → left = 5 |
5 | "cb" | 3 |
| 7 | 'b' | 'b' 在窗口内（6 ≥ 5），移动左侧边界 → left = 7 |
7 | "b" | 3 |
分步说明
我们先厘清一下这个滑动窗口移动的过程：
- 定义一个空的滑动窗口，然后定义滑动窗口的左侧边界，设置默认为 0；用
enumerate()解析这个字符序列，返回索引和字符。 - 根据这个字符去检查每次读取到一个字符都放入
char_sequence字典中。 - 每读取一个字符就检查之前是否有这个字符。注意，只检查当前的窗口大小，不是从索引 0 开始检查，所以需要
>= left，如果之前有这个字符，那么就更新左侧字符为滑动窗口中首次出现这个字符的下一个位置。 - 把当前的字符插入到
char_sequence中，如果之前有这个字符，就更改为最新的索引。 - 最后计算长度的时候，由于之前
left是在重复字符索引的下一个位置，而右侧又是在索引字符上，所以计算长度的时候，需要right - left + 1
以 abcdgfckjdd 为例：
0 1 2 3 4 5 6 7 8 9 10
a b c d g f c k j d d
- 1 个无重复字符的最长子串
这个字符序列中，第一个字符为 a，索引为 0，左侧的边界为索引 0 的字符（默认边界），然后右侧边界为 a 字符的索引，索引也是 0
把当前的字符插入到 char_sequence
char_sequence 为 {'a': 0}
现在的 max 为1
0 1 2 3 4 5 6 7 8 9 10
a b c d g f c k j d d
--- 2 个无重复字符的最长子串
现在 ab 都是不重复的
char_sequence 为 {'a': 0, 'b': 1}
现在的 max 为2
0 1 2 3 4 5 6 7 8 9 10
a b c d g f c k j d d
----- 3 个无重复字符的最长子串
现在 abc 都是不重复的
char_sequence 为 {'a': 0, 'b': 1, 'c': 2}
现在的 max 为3
0 1 2 3 4 5 6 7 8 9 10
a b c d g f c k j d d
------- 4 个无重复字符的最长子串
现在 abcd 都是不重复的
char_sequence 为 {'a': 0, 'b': 1, 'c': 2, 'd': 3}
现在的 max 为4
0 1 2 3 4 5 6 7 8 9 10
a b c d g f c k j d d
--------- 5 个无重复字符的最长子串
现在 abcdg 都是不重复的
char_sequence 为 {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'g': 4}
现在的 max 为5
0 1 2 3 4 5 6 7 8 9 10
a b c d g f c k j d d
----------- 6 个无重复字符的最长子串
现在 abcdgf 都是不重复的。
char_sequence 为 {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'g': 4, 'f': 5}
现在的 max 为6
0 1 2 3 4 5 6 7 8 9 10
a b c d g f c k j d d
------------- 存在重复字符
当前的的 c （索引为 6）与索引为 2 的 c 重复
符合条件 if char in char_sequence and char_sequence[char] >= left:，所以进行偏移。
left 偏移到当前字符相同的字符后一个字符，即 char_sequence[char] + 1，也就是 3
更新字符的最新位置 char_sequence[char] = right，也就是把原来的 'c': 2 更新为 'c': 6
当前的 char_sequence 为 {'a': 0, 'b': 1, 'c': 6, 'd': 3, 'g': 4, 'f': 5} （长度和上面一样，但是更新了 c）
可以理解为：
0 1 2 3 4 5 6 7 8 9 10 a b c d g f c k j d d ---- ------- 存在重复字符
现在的因为上一次的 len 为 6，现在的 len 为 6 - 3 + 1 = 4，保留的 max
然后继续右侧偏移。
0 1 2 3 4 5 6 7 8 9 10
a b c d g f c k j d d
---- --------- 没有重复字符
没有重复字符。
char_sequence 为 {'a': 0, 'b': 1, 'c': 6, 'd': 3, 'g': 4, 'f': 5, 'k': 7}
现在的因为上一次的 len 为 6，现在的 len 为 7 - 3 + 1 = 5
max 为 6
0 1 2 3 4 5 6 7 8 9 10
a b c d g f c k j d d
---- ----------- 没有重复字符
char_sequence 为 {'a': 0, 'b': 1, 'c': 6, 'd': 3, 'g': 4, 'f': 5, 'k': 7, 'j': 8}
现在的因为上一次的 len 为 6，现在的 len 为 8 - 3 + 1 = 6
max 为 6
0 1 2 3 4 5 6 7 8 9 10
a b c d g f c k j d d
---- ------------- 有重复字符
更新前面的 d 为 9
char_sequence 为 {'a': 0, 'b': 1, 'c': 6, 'd': 9, 'g': 4, 'f': 5, 'k': 7, 'j': 8}
可以理解为
0 1 2 3 4 5 6 7 8 9 10 a b c d g f c k j d d ---- ----------- 有重复字符
现在的因为上一次的 len 为 6，现在的 len 为 9 - 4 + 1 = 6
max 为 6
0 1 2 3 4 5 6 7 8 9 10
a b c d g f c k j d d
---- --------- - 有重复字符
char_sequence 为 {'a': 0, 'b': 1, 'c': 6, 'd': 10, 'g': 4, 'f': 5, 'k': 7, 'j': 8}
现在的因为上一次的 len 为 6，现在的 len 为 10 - 10 + 1 = 1
max 为 6
- 时间复杂度： O(n)
- 每个字符最多被访问两次（一次被 right 访问，一次被 left 访问）
- 空间复杂度： O(min(m,n))
- 哈希表最多存储 min(m,n) 个字符
针对数组优化的版本
对于 ASCII 字符，可以用数组代替哈希表，提高常数因子的性能：
class Solution {
public:int lengthOfLongestSubstring(string s) {vector<int> charIndex(128, -1); // ASCII字符表int maxLen = 0;int left = 0;for (int right = 0; right < s.length(); right++) {char currentChar = s[right];// 如果字符在当前窗口内，移动左指针if (charIndex[currentChar] >= left) {left = charIndex[currentChar] + 1;}charIndex[currentChar] = right;maxLen = max(maxLen, right - left + 1);}return maxLen;}
};
- 时间复杂度： O(n)
- 空间复杂度： O(m)，m = 128（ASCII字符集大小）
五、关键技巧
1. 滑动窗口模式
-
核心思想： 维护一个动态窗口，通过移动左右边界来满足约束条件
-
适用场景： 连续子数组/子串问题，特别是有约束条件的情况
-
模板结构：
int left = 0; for (int right = 0; right < n; right++) {// 扩展窗口，加入 s[right]// 当窗口不满足条件时，收缩窗口while (window_is_invalid) {// 移除 s[left]left++;}// 更新结果 }
2. 哈希表优化
- 字符位置记录： 使用哈希表记录字符最后出现的位置
- 快速查重： O(1) 时间复杂度检查字符是否重复
- 索引跳跃： 直接跳到重复字符的下一个位置，避免逐个移动
3. 边界处理技巧
- 初始化： left = 0, 哈希表初始为空或 -1
- 越界检查： 确保 charIndex[currentChar] >= left
- 更新时机： 每次都更新字符位置，无论是否重复
六、总结
核心要点
- 滑动窗口是解决子串问题的利器，特别适合有约束条件的连续子串问题
- 哈希表提供 O(1) 的查找和更新，是滑动窗口的最佳伙伴
- 双指针减少不必要的重复计算，将暴力 \(O(n^3)\) 优化到 \(O(n)\)
- 边界条件处理至关重要，注意指针越界和哈希表状态
常见错误
- 忘记更新字符位置，导致左指针移动错误
- 边界判断遗漏，特别是
charIndex[currentChar] >= left条件 - 窗口长度计算错误，注意是
right - left + 1 - 哈希表操作混乱，插入、删除、查找的时机把握不准