不定长滑动窗口（求最长）
把"定长滑窗"升级到"while 收缩"通用模板，统一拿下 LC 3 / 424 / 340 / 904
1. 核心原理
定长滑窗的"窗口大小恒为 k"是一种强约束：每次右端进 1 个、左端必出 1 个，节奏机械。但北美面试更高频的形态是这样：
"给定数组/字符串，求满足某个条件的最长连续子区间长度。"
条件可能是"无重复字符"（LC 3）、"最多 k 个不同字符"（LC 340）、"窗口内 0 的个数 ≤ k"（LC 1004）、"替换至多 k 次后全相同"（LC 424）。这些题目窗口长度不再固定——它能多长，取决于条件什么时候被破坏。
从定长升级到不定长的关键
只需要换一个动作：把"左端必定弹出"换成"左端条件性收缩"。三段式模板从
in → out (固定) → update-ans升级为
in → while 不满足条件: shrink → update-ans关键洞察一句话：右指针稳步前进一格不回头，左指针在条件被破坏时才一步一步前进直到条件重新满足。两个指针都只朝右走，每个元素至多进窗口 1 次、出窗口 1 次，所以总操作数是 $O(n)$（均摊证明见第 5 节）。
与定长的对比
| 维度 | 定长滑窗 | 不定长滑窗（求最长） |
|---|---|---|
| 窗口大小 | 恒为 k | 动态变化 |
| 左指针推进时机 | 每步固定推进 1 格 | 只在条件被破坏时收缩 |
| out 逻辑 | if i >= k: 一次性弹 1 个 | while not_ok(): 可能弹多个 |
| 答案更新 | 窗口满 k 时更新 | 每轮 while 收敛后都更新 |
| 复杂度 | $O(n)$ | $O(n)$（均摊） |
北美面试切入点
LC 3 (Longest Substring Without Repeating Characters) 是这套模板的母题，LC 340 → LC 424 → LC 904 等都是它的小幅变形。
把这套"通用三段式"记熟，整张表上的 4 道题（LC 3 / 1004 / 340 / 424 / 904）都可以用同一个骨架写完，只换 add / remove / not_satisfied 三个钩子。
2. 通用模板
把脑子里的伪代码先固化下来，所有不定长求最长的题都是它的变体：
l = 0
for r, x in enumerate(s):
add(x) # 1) in: 右端纳入新元素
while not_satisfied(): # 2) shrink: 条件破坏则收缩左端
remove(s[l])
l += 1
ans = max(ans, r - l + 1) # 3) update: 每轮收敛后更新最长长度三段对应的钩子在不同题里的具体化：
- add / remove：通常是
set.add/set.discard或cnt[x] += 1/cnt[x] -= 1 - not_satisfied：LC 3 是
s[r] 在 set 中已经出现，LC 340 是len(cnt) > k，LC 1004 是窗口内 0 的个数 > k - r - l + 1：当前窗口长度，因为这是"求最长"，所以每轮 while 退出后都要更新一次
3. ASCII 图解
以 LC 3 在字符串 "abcabcbb" 上为例，演示窗口如何"先扩张、再收缩、再扩张"。set 维护窗口内字符集合，r 每步前进 1，l 仅在新字符已出现时收缩：
Step 1: [a] b c a b c b b set={a}, ans=1
l (in: +a)
r
Step 2: [a b] c a b c b b set={a,b}, ans=2
l r (in: +b)
Step 3: [a b c] a b c b b set={a,b,c}, ans=3
l r (in: +c)
Step 4: 不满足: s[r]='a' 已在 set 中, 收缩左端
a [b c a] b c b b set={b,c,a}, ans=3
l r (out: -a, in: +a)
Step 5: 不满足: s[r]='b' 已在 set 中, 继续收缩
a b [c a b] c b b set={c,a,b}, ans=3
l r (out: -b, in: +b)
Step 6: 不满足: s[r]='c' 已在 set 中
a b c [a b c] b b set={a,b,c}, ans=3
l r (out: -c, in: +c)
Step 7: 不满足: s[r]='b' 已在 set 中, 连续收缩两次直到弹出旧 b
a b c a b [c b] b set={c,b}, ans=3
l r (out: -a,-b, in: +b)
Step 8: 不满足: s[r]='b' 已在 set 中, 再次收缩
a b c a b c b [b] set={b}, ans=3
l
r (out: -c,-b, in: +b)注意三个关键现象：
- Step 3 → Step 4：右指针碰到重复字符
a时，左指针不是跳到 a 后面，而是逐个 remove 直到 a 被踢出。这种"一步一步"的方式是均摊 $O(n)$ 的关键 - Step 7：一次
while可能触发多次 shrink（连续弹了两个字符），不是只弹 1 个 - 最终
ans = 3，出现在多个窗口（abc/bca/cab/abc），第一次达到是 Step 3
不定长滑动窗口（求最长）
LeetCode 3 · 无重复字符的最长子串
4. 母题精讲
LeetCode 3. Longest Substring Without Repeating Characters
题目（中文翻译）：给定字符串 s，找出其中不含重复字符的最长子串的长度。
样例 1：
输入: s = "abcabcbb"
输出: 3
解释: 最长无重复子串是 "abc", 长度为 3.样例 2：
输入: s = "bbbbb"
输出: 1
解释: 最长无重复子串是 "b", 长度为 1.思路推导
为什么用 hash set？ 我们需要 $O(1)$ 时间判断"窗口里是否已经有了 s[r]"，以及 $O(1)$ 时间增删元素。Python 的 set 平均 $O(1)$，是天然选择。如果改用 list，in 是 $O(n)$，整体退化到 $O(n^2)$。
为什么左指针只前进不回退？ 这是滑动窗口能均摊 $O(n)$ 的核心性质。直觉证明：当我们因为 s[r] 重复而收缩 l 时，"重复"这件事只可能发生在 s[r] 与窗口里某个旧字符冲突。一旦把旧字符弹出，l 之前的位置就永远不可能比当前位置更好——因为更左的起点只会让窗口包含更多字符、更容易出现重复。所以左指针单调右移，不需要"回头看"。
均摊 $O(n)$：右指针走 $n$ 步，左指针在最坏情况下也只走 $n$ 步（永远跟不上右指针）。每个字符最多入 set 1 次、出 set 1 次，总操作数 $\leq 2n$。
Python 工业级实现
from typing import Set
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# window 是窗口内出现过的字符集合, set 提供 O(1) 增删查
window: Set[str] = set()
l = 0 # 左指针, 窗口左边界 (含)
ans = 0 # 历史最长长度
for r, ch in enumerate(s):
# ---------- 2) shrink: 在 add 之前先把重复挤出去 ----------
# 注意是 while 不是 if: 理论上 ch 在窗口里只会出现 1 次,
# 所以这里 while 最多执行 1 次完整循环就会退出.
# 用 while 写法的好处是与"最多 k 个不同字符"等题型完全同构.
while ch in window:
window.remove(s[l])
l += 1
# ---------- 1) in: 右端纳入新字符 ----------
window.add(ch)
# ---------- 3) update-ans: 当前窗口已合法, 更新最长 ----------
# r - l + 1 是当前窗口长度 (闭区间 [l, r])
cur_len = r - l + 1
if cur_len > ans:
ans = cur_len
return ansC++ 备份实现
#include <unordered_set>
#include <string>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> window;
int l = 0, ans = 0;
for (int r = 0; r < (int)s.size(); ++r) {
char ch = s[r];
// shrink: 把重复字符挤出去
while (window.count(ch)) {
window.erase(s[l]);
++l;
}
// in
window.insert(ch);
// update-ans
ans = max(ans, r - l + 1);
}
return ans;
}
};代码逐段讲解
变量含义：
window：滚动维护的"当前窗口内出现过的字符集合"，是这道题的核心状态l：闭区间左边界。s[l .. r]是当前窗口ans：从初始 0 开始单调不减地记录历史最长
循环不变量：每轮迭代结束时，window == set(s[l .. r]) 且窗口内无重复。这是 update-ans 那一行能直接信任 r - l + 1 的前提。
为什么 while 不是 if？ 对于 LC 3 而言，if 确实够用——同一个字符只能重复一次，shrink 一次就够。但写成 while 是为了让模板可迁移：到了 LC 340（最多 k 个不同字符）、LC 1004（窗口内 0 的个数 ≤ k），shrink 一次可能不够，需要持续弹直到条件再次满足。统一用 while 写，跨题型零成本。
为什么 shrink 写在 add 之前？ 两种写法都对，但顺序不同：
- 本文写法（shrink 先 / add 后）：进入循环时
window是"加入 ch 之前的快照"，判断ch in window直接对应"是否会产生重复" - 另一种（add 先 / shrink 后）：进入循环后立即
add(ch)，shrink 条件改成cnt[ch] > 1，需要把 set 升级为 Counter
前一种更简洁，本章统一沿用。
边界 l = 0 与 r - l + 1：当 l = r = 0 时窗口长度 = 1，对应单字符场景。空串时 for 循环根本不执行，ans 保持 0，行为正确。
5. 复杂度分析
- 时间复杂度：$O(n)$ — 均摊证明：右指针
r从 0 走到 n-1 共 n 步；左指针l全程单调右移，最坏也只走 n 步。每个字符最多set.add一次、set.remove一次，每次操作平均 $O(1)$，总操作数 $\leq 2n + O(n)$ = $O(n)$ - 空间复杂度：$O(\min(n, |\Sigma|))$ —
window大小上界是字符集大小 $|\Sigma|$ 与字符串长度 n 的较小值。ASCII 时 $|\Sigma| = 128$，扩展 ASCII $|\Sigma| = 256$，Unicode 理论上 $|\Sigma| = 2^21$ 但实际远小于 n - 暴力 $O(n^2 \cdot k)$ vs. 滑窗 $O(n)$ 的真实差距：暴力枚举每个起点 i（n 种），再枚举每个终点 j（n 种），再判断
s[i..j]是否含重复（k 次扫描），是 $O(n^3)$。即便用 set 判重压到 $O(n^2)$，当 $n = 5 \times 10^4$ 时也要 $2.5 \times 10^9$ 次操作，LeetCode 直接 TLE。滑窗只要 $5 \times 10^4$ 次
类似的去重 / 不重复段统计在流式数据处理里也很常见，O(n) 与 O(n²) 的差距决定能否在线处理。
6. 边界条件拆解
(1) 空串 / 单字符串：s = "" 时 n = 0，for 循环根本不执行，ans 保持初值 0——这是正确答案。s = "a" 时只走一次循环，window = {a}、l = 0、r = 0、ans = 1，也正确。不需要任何特判，模板天然处理这两个 corner case。
(2) 全相同字符 "aaaa"：第一次循环 window = {a}、ans = 1；第二次进入时 ch = 'a' 已在 set 中，shrink 弹出 s[0]='a'、l = 1、window = {}，然后 add 进新 a、ans = max(1, 1) = 1。后续每一步都是这个模式，最终 ans = 1。说明 while 的存在让"每一步都收敛"成立，即使在退化输入上也不会越界。
(3) Unicode（汉字 / emoji）：Python 的 str 默认按 Unicode 码点遍历，set 也直接支持任意 str。例如 s = "你好你"：迭代时 ch 依次是 '你' / '好' / '你'，第三步检测到 '你' in window，shrink 弹出前两个字符。关键提醒：不要为了优化而用 [0] * 128 这种 ASCII 数组，否则汉字会越界。emoji 更危险，单个 emoji 可能由多个 code point（surrogate pair / ZWJ 序列）组成，如果题目允许 emoji，建议先 import unicodedata 做规范化。
(4) 巨长 ASCII 字符串的常数优化：当题目保证仅 ASCII（如 LeetCode 3 的 constraint "consists of English letters, digits, symbols and spaces"），可以把 set 换成 last = [-1] * 128（记录每个字符上次出现的位置），用下标查找代替 hash 查找，常数大约提速 2-3 倍。代码示例：
def lengthOfLongestSubstring(self, s: str) -> int:
last = [-1] * 128 # 仅 ASCII 时的常数优化
l, ans = 0, 0
for r, ch in enumerate(s):
code = ord(ch)
if last[code] >= l:
l = last[code] + 1 # 直接跳到旧位置后面
last[code] = r
ans = max(ans, r - l + 1)
return ans这是工业代码里更常见的写法（直接跳跃 l，跳过逐个 remove），但面试时建议先写 set 版本展示思路，再口头提到这个优化——分两步走更容易拿到信号。
7. 通用模板
下面这 8 行骨架覆盖本章所有"求最长"题：
# 不定长滑动窗口 (求最长) 三段式模板
l, ans = 0, 0
for r, x in enumerate(arr):
add(x) # 1) in: 右端纳入
while not_satisfied(): # 2) shrink: 条件破坏则收缩左端
remove(arr[l])
l += 1
ans = max(ans, r - l + 1) # 3) update: 每轮收敛后更新最长
return ans其中：
add(x)/remove(x)：通常是set.add/discard或cnt[x] += 1 / -= 1not_satisfied()：题目条件的"破坏判定"，如x in window/len(cnt) > k/zeros > k
8. 热身题：LC 1004 Max Consecutive Ones III
题目：给定 0/1 数组 nums 和整数 k，可以把至多 k 个 0 翻成 1，求翻完后最长连续 1 的长度。
关键洞察：把题面翻译成滑窗约束——"窗口内 0 的个数 ≤ k" 时，整个窗口都能变成全 1。问题立刻变成"求满足窗口内 0 的个数 ≤ k 的最长窗口长度"，直接套模板：
from typing import List
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
l, zeros, ans = 0, 0, 0
for r, x in enumerate(nums):
if x == 0:
zeros += 1 # in: 0 的计数 +1
while zeros > k: # shrink: 0 太多了就收缩
if nums[l] == 0:
zeros -= 1
l += 1
ans = max(ans, r - l + 1) # update
return ans5 行讲解：
- 不需要 set / hashmap，只需一个标量
zeros计窗口里 0 的个数 - shrink 条件是
zeros > k——只有 0 超额时才需要收缩 - 收缩时若弹出的是 0，
zeros -= 1；若弹出的是 1，不影响zeros - update 阶段所有窗口都已合法（zeros ≤ k），直接取
r - l + 1 - 这就是"把现实约束翻译到滑窗约束"的能力——后面的 LC 424 / 340 / 904 都是同一招