滑动窗口与子串专题：模板原理、易错点与面试讲题亮点

刷过 hot100 的人，基本都会在“滑动窗口、子串”这块卡上一段时间。不是题有多难，而是这几道题长得太像，解法却各有各的细节：有的要固定窗口长度，有的要动态收缩，有的收缩完才更新答案，有的先更新再收缩。我见过不少同学刷完这几道热门题，能对着题解把代码敲出来，但换一道同类题立刻发懵。这篇文章就把 hot100 里滑动窗口、子串这个专题彻底拆开：先讲清楚窗口模板背后的原理，再逐题过一遍易错点，最后聊聊面试的时候怎么把这部分讲出亮点。适合两类人：一类是刚开始刷题、准备面试的开发者；另一类是刷完一遍但总觉得没吃透、想系统梳理的人。

1. 这个专题为什么值得单独拎出来刷

1.1 暴力解法到滑动窗口的演进逻辑

拿最常见的子串题举例：给你一个字符串，找满足条件的最长或最短连续子串。第一反应基本都是暴力枚举——两层 for 枚举所有起点和终点，再花一层循环去校验条件，复杂度直接 O(n^3)。如果字符串不长还能忍，一旦长度到 10^5 级别，这个复杂度就是灾难。

滑动窗口优化的核心在于：它没有重新枚举每一个子串，而是利用“子串之间高度重叠”这个特点，把上一次的判断结果增量继承下来。你往右扩展一个字符，只需要更新一点点状态；窗口左端收缩时，也只撤销一点点状态。整个过程像一条传送带，右端不停进料，左端按需出料，中间的产品就是当前窗口对应的子串。

这就解释了为什么滑动窗口总是 O(n) 而不是 O(n log n)：每个字符进窗口一次、出窗口一次，均摊下来每步操作都是 O(1)。面试官看到你能把“枚举所有子串”优化成“滑动一次窗口”，至少能确认你理解了连续区间类问题的基本优化方向。

1.2 识别滑动窗口题型的三个信号

不是所有数组/字符串题都能用滑动窗口，硬套模板反而容易错。我刷这个专题总结出三个信号，同时满足再往窗口上想。

第一个信号是求连续子串或连续子数组。题目里出现“子串”“子数组”“连续区间”这类词，是窗口题的基本盘。注意“子序列”不算，那个通常走动态规划。第二个信号是窗口状态可以进行增量维护，比如字符频次、不同字符数量、最大频次、区间和。这些信息都能在你右扩和左缩时用 O(1) 更新，不需要重新计算整个窗口。第三个信号最重要，也是最容易被忽略的：左端指针不能回头。窗口只有在右端扩展、左端追赶时保持单调移动，才能保证没有漏解。换句话说，随着右端不断右移，问题的可行解边界也必须单调右移。子串求和、字符覆盖这类问题天然满足这个性质，而一些需要回退搜索的题就不适合。

很多人刷到后面会混淆“双指针”和“滑动窗口”，其实滑动窗口就是双指针的一种特例，只是它额外强调窗口状态的可维护性。能分清这一点，后面看题解会顺畅很多。

1.3 固定窗口与可变窗口怎么选

子串题按窗口形态分两类。固定窗口是指窗口长度恒定，比如找所有长度为 k 的满足条件的子串；可变窗口是指窗口长度随条件变化，比如找无重复字符的最长子串时，窗口会先变长再收缩。hot100 里大部分是可变窗口，但也有固定窗口的经典题。

判断方法很简单：如果答案本身一定要有固定长度，基本就是固定窗口，窗口超出预定长度就收缩；如果答案只要求条件满足，长度自行伸缩，就是可变窗口。两类模板只是收缩条件不同，其他骨架完全一样。我后面给代码模版时会直接把这层区别标出来，方便你对照。

2. 一套模板通吃大部分子串题

2.1 可变窗口模板速记

不管题目怎么变，可变窗口的骨架都是这四步：右指针扩展，更新窗口状态；判断窗口是否不满足条件；不满足就收缩左指针并撤销状态；窗口满足条件后更新答案。下面这份模板用的是字符频次 Counter，算是最通用的形态。

from collections import Counter def sliding_window_template(s: str): n = len(s) window = Counter() left = 0 ans = 0 for right in range(n): # 1. 扩展右端，把新字符纳入窗口 window[s[right]] += 1 # 2. 窗口不满足题设条件时，收缩左端 while not valid(window): window[s[left]] -= 1 if window[s[left]] == 0: del window[s[left]] left += 1 # 3. 窗口已经满足条件，此时更新答案 ans = max(ans, right - left + 1) return ans

valid 函数就是题目条件的抽象，实际写的时候可能是一段判断、一个计数器、甚至一个布尔表达式。注意一个细节：窗口字符计数归零后，我习惯显式删掉这个键，否则后续用 len(window) 统计窗口内不同字符数量时会出错。这个坑我踩过，后面常见问题里还会细说。

2.2 固定窗口模板速记

固定窗口模板更短，本质是限制窗口最大长度不减错，比如长度超过 k 就必须收缩左端一步，让窗口保持固定长度滚动。

def fixed_window_template(s: str, k: int): n = len(s) window = Counter() ans = [] for right in range(n): window[s[right]] += 1 if right - left + 1 > k: window[s[left]] -= 1 if window[s[left]] == 0: del window[s[left]] left += 1 if right - left + 1 == k: # 检查当前窗口是否满足条件 if check(window): ans.append(left) return ans

固定窗口的关键是“长度超了就收缩一次”用的是 if 而不是 while，因为每次 right 右移一位，left 最多只需要右移一位就能恢复长度。如果这里误写成 while，逻辑也能走通，但白白多做判断，代码也显得不够利索。

2.3 状态容器选型：数组还是哈希表

窗口状态最常见的两种容器是定长数组和哈希表。如果题目明确说明只包含小写英文字母，用一个长度为 26 的数组做字符频次是非常好的选择，访问快、也不用处理删除键的问题。如果字符串可能包含任意 ASCII 或 Unicode 字符，数组可以开到 128 或 256，但更大字符集时老老实实上哈希表。

哈希表相比定长数组有一个额外好处：可以直接用 len(window) 拿到窗口内不同字符的数量，这在做“最长不重复子串”这类题时非常方便。缺点就是刚才说的，计数归零时需要删除键，否则长度统计失真。所以我的习惯是：小字符集优先数组，大字符集用 Counter，两种方式都要能随手写出来。

3. hot100 里的重点题逐题拆解

3.1 无重复字符的最长子串

这题是可变窗口的入门题，也是很多人口诀里的“滑动窗口第一课”。维护窗口内每个字符最近一次出现的位置，右端每次扩展字符 ch 时，如果 ch 在窗口内已经出现过，就把左端跳到上个出现位置的下一个位置。这个写法可以省掉 while 循环，速度更快。

def length_of_longest_substring(s: str) -> int: last = {} left = 0 ans = 0 for right, ch in enumerate(s): if ch in last and last[ch] >= left: left = last[ch] + 1 last[ch] = right ans = max(ans, right - left + 1) return ans

有个细节值得说：last[ch] >= left 这个判断不能省。因为 last 字典里可能保存着这个字符在很久以前出现的位置，而那个位置已经被窗口甩到左边了。如果直接用 last[ch]，左指针可能会往回跳，那就违反了单调性，结果必错。这个边界是面试时高频追问点，答出来很加分。

还有一个常见变体是维护一个哈希集合，遇到重复字符就循环收缩左端，把移出的字符从集合里删掉。两种写法思想一致，后者更贴近通用模板，前者性能更好。如果面试时没有时间压力，两种都讲一遍反而更能体现熟练度。

3.2 最小覆盖子串

这题比上一题复杂一个档次，因为窗口要同时满足多个字符的覆盖条件。核心思路是：用 need 数组记录目标串 t 中每个字符还需要多少个，total 表示还需要多少种不同字符。只有当某类字符的 need 归零时，total 才减一；当 total 等于 0，说明窗口已经完整覆盖了 t 中所有字符。

def min_window(s: str, t: str) -> str: if not s or not t: return "" need = Counter(t) total = len(need) left = 0 start, min_len = 0, float("inf") for right, ch in enumerate(s): if ch in need: need[ch] -= 1 if need[ch] == 0: total -= 1 while total == 0: if right - left + 1 < min_len: min_len = right - left + 1 start = left left_ch = s[left] if left_ch in need: if need[left_ch] == 0: total += 1 need[left_ch] += 1 left += 1 return "" if min_len == float("inf") else s[start:start + min_len]

注意更新答案的位置：这题是在窗口满足条件后、尝试收缩左端的过程中更新，因为我们找的是最短覆盖子串，窗口越大越不可能成为答案。每次收缩左端时，一旦即将破坏覆盖条件，就意味着刚才那个窗口是当前右端点下的最短合法窗口，要在破坏前记录长度。这个时机非常容易错，建议自己手推一个例子走一遍。

3.3 找到字符串中所有字母异位词

这题和“字符串的排列”几乎是同一道题，区别只是返回所有起点还是只返回 true。异位词意味着长度相同、字符频次相同，所以窗口本质是固定长度 len(p)。当窗口长度超过 len(p) 时，left 右移一步，保持窗口长度恒定；当窗口长度正好等于 len(p) 且字符频次完全一致时，记录起点。

def find_anagrams(s: str, p: str) -> list[int]: if len(s) < len(p): return [] need = Counter(p) window = Counter() left = 0 ans = [] for right, ch in enumerate(s): window[ch] += 1 if right - left + 1 > len(p): if window[s[left]] == 1: del window[s[left]] else: window[s[left]] -= 1 left += 1 if right - left + 1 == len(p) and window == need: ans.append(left) return ans

这个写法里 window == need 直接比较两个 Counter 对象，Python 的 Counter 重载了相等比较，非常方便。有些解法会用 diff 记录不同字符数来优化，原理一样，但比较 Counter 更适合面试时快速写对。如果你担心频繁构造 Counter 有开销，也可以在收缩 left 后手工更新一个 diff 计数，不过 hot100 的数据规模下这份代码完全够用。

3.4 最长重复字符替换（进阶扩展）

这题不算典型子串题，但它非常考验对窗口收缩条件的理解。给定字符串 s 和最多替换次数 k，求把窗口改成全部相同字符后能形成的最大长度。窗口的合法条件是：窗口长度减去窗口内出现次数最多的字符数量，不能超过 k。这个差值就是需要替换的字符数。

def character_replacement(s: str, k: int) -> int: cnt = Counter() left = 0 max_freq = 0 for right, ch in enumerate(s): cnt[ch] += 1 max_freq = max(max_freq, cnt[ch]) if right - left + 1 - max_freq > k: cnt[s[left]] -= 1 left += 1 return len(s) - left

这里有个很反直觉的点：当窗口不满足条件、left 右移并减少字符频次时，max_freq 并没有同步更新。按道理说，如果移出的是当前频次最高的字符，max_freq 应该变小才对，但这里故意不减。原因是什么呢？max_freq 在这里扮演的是“历史最大频次”的角色，只要它曾经达到过某个值，说明存在过一个包含这么多重复字符的窗口；而我们要找的是最长长度，这个历史最大值不会导致答案被高估，反而能让窗口尽量少收缩。这个技巧理解起来有点绕，建议拿一个具体例子模拟几遍。如果实在接受不了，也可以每次重新算 max_freq = max(cnt.values())，但那样复杂度会高一些，面试时能讲清楚“历史最大值不减”的话，印象分会高不少。

4. 手撕代码时最容易踩的坑

4.1 收缩用 while 还是 if，千万别搞反

固定窗口题基本用 if 收缩一次，可变窗口题基本用 while 持续收缩，这是大方向。但有一个特例：最小覆盖子串里收缩条件不是简单的“窗口非法”，而是“窗口已合法但要尝试更短”，所以用的是 while 一直收缩到即将不合法为止；无重复字符最长子串如果用通用 Counter 模板，也是 while 把重复字符清理干净。

很多人在固定窗口模板中误用 while，左端一步到位，虽然结果可能对，但窗口长度会突然小于预定长度，状态就乱了。反过来，可变窗口模板中误用 if，窗口还没恢复到合法状态就开始更新答案，结果必然偏大。遇到这类问题，建议先写注释标明“收缩到合法为止”还是“收缩一步保持长度”，再动手写代码。

4.2 答案更新的位置决定了结果是“最大”还是“最小”

我见过一个比较经典的问题：同一道“无重复字符最长子串”，有人把 ans 更新写在收缩前，结果所有子串中都包含重复字符，答案被虚大。原因很简单，更新答案前必须保证窗口状态满足题设条件。最长类题目通常先收缩到合法再更新答案；最短类题目则相反，要先有一个合法窗口，然后尝试收缩，在收缩过程中不断用更短的窗口去更新答案。

记住这个原则能规避一大半错误：更新答案的位置紧扣“窗口合法”这个时刻。合法是更新的前提，而不是扩展的前提。

4.3 计数器维护时的边缘 bug

计数器是子串题里出错率最高的地方。第一种错误是只增不减，左端收缩时忘了把对应字符的计数减掉，窗口长度变短但状态数据没变，后面的判断全部失真。第二种错误是归零后不删键，导致 len(window) 统计出错，这类 bug 很隐蔽，字符串稍长一点才暴露。第三种错误是哈希表存索引时，忘记判断历史索引是否还在当前窗口范围内，导致左指针回退，直接破坏单调性。

我自己的排查经验是：遇到计数器相关 bug，先在纸上把 left、right、窗口内容列出来，然后手动走一步，对比代码里的窗口状态是否跟纸面一致。窗口问题十有八九能靠这个方法查出来，比瞎调试快得多。

4.4 常见问题速查表

这类 bug 基本都有固定模式，刷题多了就有肌肉记忆。我一般建议准备一个本地调试模板，把窗口的 left、right、窗口内容打印出来，跑几个小用例，很快能定位问题。

5. 从“会写代码”到“能讲给面试官听”

5.1 为什么这个专题被面试官频繁点名

滑动窗口代码量不大，但信息密度很高。它能考察你对连续区间的感觉、对复杂度的控制、对边界条件的处理，外加一点单调性的直觉。一个候选人能否把“为什么窗口收缩是正确的”讲清楚，基本能反映他是不是真的理解算法，而不是背了模板。这也是 hot100 把它和双指针、子串并列成一个专题的原因。

很多人觉得这类题简单，面试时草草讲完，结果被追问一句“你能证明窗口不会漏解吗”就卡壳了。实际上不用会严格的数学证明，能说出以下逻辑就够了：右指针每前进一步，都会把以该位置为右端的所有可能窗口纳入考虑；左指针只会在右指针固定的前提下单调右移，但不会跳过任何一个“潜在合法窗口”的起点。翻译成人话就是，该看的位置我们都看过了，只是没有暴力枚举而已。

5.2 五步讲题法：照着练几次后形成肌肉记忆

我复盘过不少模拟面试，发现能把一道窗口题讲清楚的人，基本都遵循一套固定套路。第一步，先说窗口里维护的是什么，比如“窗口里维护一个字符频次表，表示当前子串中每个字符出现的次数”。第二步，说清楚右指针扩展时状态怎么更新。第三步，讲明左指针什么时候收缩、收缩到什么程度。第四步，说明什么时候更新答案，以及为什么这个时机对应最长或最短。第五步，用一个小例子演示一遍过程，顺带补充时间复杂度和空间复杂度。

这样讲完之后，面试官大概率只会追着一个点深挖：为什么这里用 while 而那里用 if。这时候你前面踩过的那些坑，反而成了你的谈资。我甚至在面试时主动说“这里的收缩如果写成 if 会漏掉某些场景，我之前写错过”，面试官通常会觉得你比只会背答案的候选人真实得多。

5.3 相似题的延展：从最长最短到恰好

hot100 里的子串题主要覆盖了“最长”“最短”“固定长度”三种问法。实际上子串题还有第四种常见问法：“恰好等于某个值”。比如“恰好包含 k 种不同字符的子数组数量”，这种题用到的是一个经典技巧：恰好 K 等于最多 K 减去最多 K-1。用两次可变窗口分别求出“最多 k 种”的窗口合法数量，然后相减，就能绕开“恰好”带来的复杂收缩逻辑。

这个技巧我是在刷了若干道计数窗口题之后才总结出来的。它的价值在于提醒你：子串题的难点往往不在模板本身，而在如何把题目要求翻译成窗口的合法条件。如果面试中遇到“恰好”类问题，主动说出这个减法技巧，会是个不错的差异化亮点。

6. 写在最后的一点真实体会

我以前带过一个新人，刷完这五道题之后跟我说，感觉每道题都是滑动窗口，又感觉每道题的代码都不一样，记不住。我说你记住的不是代码，而是状态维护逻辑：窗口是什么、条件是什么、什么时候收缩、什么时候更新答案。这四个问题代码里写得多丑都不怕，逻辑对了代码很快就能改对。后来他把这四句话贴到显示器边上，老老实实刷了一个星期，之后再遇到同类题，基本能独立写出来。这件事给我的感触很深：滑动窗口专题最大的价值不是那几道题本身，而是养成对“连续区间单调收缩”的条件反射。你以后做二维矩阵问题、做流式数据处理，甚至做日志区间统计，都能用上这个思维。

最后分享一个小技巧，如果你刚开始刷这个专题，不要急着背代码。先把模板抄一遍，然后合上屏幕，用手推一遍无重复字符最长子串的整个 left 和 right 移动过程，推完再打开代码对照。你能推对一遍，比抄十遍都管用。等你哪天真能在面试现场把窗口的每一步移动原因讲清楚，这个专题就算彻底拿下了。