LeetCode 3中等滑动窗口
无重复字符的最长子串 图解题解
不含重复字符的最长一段有多长？一扇伸缩窗帘从头拉到尾就知道了。
就像拉一扇可伸缩的窗帘扫过字符串：右边一格格拉开、把新字符纳进来；一旦窗内出现重复，就从左边往里收，直到重复消失——然后继续往右拉。左端只往右走、永不回退，窗帘一遍扫完，全程只存当前窗口里有哪些字符。
这道题到底在问什么
找出字符串里不含重复字符的最长一段，返回它的长度。
- s
- "pwwkew"
- 输出
- 3 （最长是 "wke"）
先想最直接的笨办法
最直白的笨办法：外层枚举每个起点 i，内层从 i 往右一格一格铺到 j，每铺一段就检查里面有没有重复，取最长的合法段。一共 O(n²) 段，慢在这两层循环上。（动画第 3 步）
最优解：一步一步想明白
- 3从每个起点往右铺，逐段查重最直白的笨办法：外层枚举每个起点 i，内层从 i 往右一格一格铺到 j，每铺一段就检查里面有没有重复，取最长的合法段。一共 O(n²) 段，慢在这两层循环上。
- 4起点每挪一位，右边全部重铺关键浪费：起点 i 每往右挪一位，右边那一截就从头重新铺、重新查重。可上一段已经知道「到哪重复」了，左端其实只需往右走、永不回退。把这层重复劳动省掉，就自然变成了滑动窗口。
- 5于是维护一个窗口 [l, r]：右指针 r 一直往右把新字符吃进窗口；一旦窗口里出现重复，就移动左指针 l 把左边挤出去，直到不再重复。左端只进不退，省掉了暴力解那层重铺，窗口里随时都是「无重复的一段」。
- 6窗口为空, 最长=0用一个集合记下「窗口里现在有哪些字符」，只记字符本身、不记下标，方便判断有没有重复。
- 7窗口 "p", 最长=1p 不在集合里，放心吃进来。窗口 = "p"，当前最长 = 1。
- 8窗口 "pw", 最长=2w 也不在集合里，吃进来。窗口 = "pw"，最长更新为 2。
- 9w 已在集合！重复想吃进 2 号位的 w，可集合里已经有 w 了——重复！这时不能直接放，得先收缩左边。
- 10移除左端 p, l→1把窗口最左边的 p 移出集合，l 前进到 1。但集合里还有 w，仍然和要吃的 w 重复，继续收缩。
- 11移除 w, l→2再把 1 号位的 w 也移出集合，l 到 2。现在集合空了，不再有 w 了。
- 12窗口 "w", 最长仍=2现在可以把这个 w 吃进来了。窗口 = "w"，长度 1，没超过之前的最长 2。
- 13窗口 "wk", 最长=2k 不在集合，吃进来。窗口 = "wk"。
- 14窗口 "wke", 最长=3e 不在集合，吃进来。窗口 = "wke"，长度 3，刷新最长记录！
- 15w 已在集合！又想吃 w，但集合里有 w，重复。收缩左边。
- 16移除 w, l→3把 2 号位的 w 移出集合，l 到 3。集合里没有 w 了。
- 17窗口 "kew", 最长仍=3吃进 w，窗口 = "kew"，长度 3，没超过最长。
- 18最长 = 3r 走到头。整个过程中窗口最长是 3（"wke"），这就是答案。
- 21滑动窗口能套很多题：最小覆盖子串、长度最小子数组、字母异位词……记住「窗口伸缩」这个手感。
- 28「右扩、不合法就左缩」是所有连续子串/子数组题的骨架：LC209 长度最小子数组（和 ≥ target 时缩）、LC76 最小覆盖子串、LC438 找异位词（定长窗口）——只换「合法条件」。看 最小覆盖子串图解 接着练，写不出来就问问 AI 助教小欧。
⚠️ 容易写错的地方
✗ 错：收缩时忘了把 s[l] 移出集合
✓ 对：l 右移的同时同步 win.remove(s[l])
否则窗口状态记错、结果偏大
✗ 错：用 if 判断收缩
✓ 对：用 while 一直缩到合法
一次可能要移除多个（如 pwwkew 的两个 w）
完整代码（Python / C++ / Java）
Python
class Solution:
def lengthOfLongestSubstring(self, s):
win = set() # 窗口里有哪些字符
l = ans = 0
for r, ch in enumerate(s):
while ch in win: # 重复→收缩左边
win.remove(s[l]); l += 1
win.add(ch) # 吃进新字符
ans = max(ans, r - l + 1)
return ansC++
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> win; // 窗口里有哪些字符
int l = 0, ans = 0;
for (int r = 0; r < (int)s.size(); r++) {
while (win.count(s[r])) { // 重复→收缩
win.erase(s[l]); l++;
}
win.insert(s[r]);
ans = max(ans, r - l + 1);
}
return ans;
}
};Java
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> win = new HashSet<>(); // 窗口里有哪些字符
int l = 0, ans = 0;
for (int r = 0; r < s.length(); r++) {
while (win.contains(s.charAt(r))) { // 重复→收缩
win.remove(s.charAt(l)); l++;
}
win.add(s.charAt(r));
ans = Math.max(ans, r - l + 1);
}
return ans;
}
}套路模板 · 滑动窗口（背下来）
# 连续子串/子数组通用骨架
l = 0
for r in range(len(s)):
加入 s[r] 到窗口
while 窗口不合法:
移除 s[l]; l += 1
更新答案(r - l + 1)int l = 0;
for (int r = 0; r < n; r++) {
add(s[r]); // 加入窗口
while (invalid()) // 不合法就收缩
remove(s[l++]);
ans = max(ans, r - l + 1);
}int l = 0;
for (int r = 0; r < n; r++) {
add(s[r]); // 加入窗口
while (invalid()) // 不合法就收缩
remove(s[l++]);
ans = Math.max(ans, r - l + 1);
}复杂度
时间复杂度
O(n)
l 和 r 各自只向右走一遍
空间复杂度
O(字符集)
集合最多存下不同字符
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 无重复字符的最长子串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么是 O(n) 不是 O(n²)？+
l 和 r 各自只往右走一遍、都不回头，加起来最多 2n 步，所以是线性。
空间到底多大？+
O(min(n, 字符集))，集合最多存下窗口里的不同字符；纯字母时是常数级。
能不能不逐个收缩、一步跳？+
能。把集合换成「字符→上次出现的下标」哈希表，遇重复时让 l 直接跳到那个下标的下一位，省掉循环收缩。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。