滑动窗口全解析：热题100四道经典题与适用边界

1. 为什么热题100里这四道题要放在一起刷

如果说我在热题100里刷得最反复的专题，滑动窗口一定排第一。原因很简单：这类题看着不难，暴力解法一下就写出来，可一旦涉及窗口收缩的时机、频次计数的边界，代码就容易写飞。这个系列到了第四篇，我决定把滑动窗口家族一次性讲透，顺便聊聊那道“误入”家族的题目。

这一篇要聊的四道题，正好覆盖滑窗家族的三种窗口形态。第3题无重复字符的最长子串，是可变长窗口中最好上手的一道；第438题找到字符串中所有字母异位词，是固定窗口的典型代表，模板化程度极高；第76题最小覆盖子串，把窗口收缩的时机玩到了极致，是热题100里最能考验边界处理能力的题目之一；最后是第560题和为K的子数组，它披着子数组的外衣，很多人第一反应也是滑窗，但实际上这题的数组元素存在负数，滑动窗口在这里根本不成立，必须换用前缀和配合哈希表来做。

这四道题放在一起有个好处：你能从一个更高的视角看清滑窗的适用边界，而不是背一个个孤立题解。第3题和第76题是“扩右收左”的动态窗口，第438题是“等长平移”的静态窗口，第560题则是反例——窗口增减不单调，指针向右滑没有任何数学依据。把这四种情况对照着刷，比自己闷头刷二十道同类题有效得多。

如果你正在准备算法面试，或刚刚开始啃热题100，这篇是完全可以独立看的，不依赖系列前文。我会从暴力解法哪里浪费了算力讲起，把每道题的关键代码、容易踩的坑、以及面试时应该怎么组织思路都过一遍。滑动窗口这个专题，吃透了就是送分题，吃不透就是每次面试都磕磕绊绊的绊脚石。

2. 滑窗直觉：为什么两根指针能省掉一层循环

2.1 暴力解法到底把时间浪费在哪了

拿第3题“无重复字符的最长子串”举例。最直观的暴力解法是枚举所有子串的左右端点，也就是两层循环，再对每个子串判断有没有重复字符，判断又需要一次遍历或者一个哈希集合。三层嵌套写下来，复杂度奔着O(n³)去了，就算用切片加集合优化，也只是把判断过程压到O(n)，整体还是O(n²)。

问题出在哪？细看暴力过程你会发现，当left固定在某个位置，right向右扩展时，很多判断是重复的。比如窗口[left, right-1]已经确认没有重复字符，现在想把right再往右移一位，你怎么知道新窗口是否合法？其实只需要看新字符在不在旧窗口里就行，不需要把整个窗口重新扫一遍。更关键的是，当窗口[left, right]已经因为有重复字符而非法时，你下一步会怎么走？暴力做法通常是让left++，然后把right拉回left，重新扩展。可right拉回去这一步，把之前扫描过的字符信息全部浪费掉了。

滑动窗口的核心改进就在这里：right指针不回头，只往右走；left指针根据条件动态收缩。这两个指针夹出来的区间就像一个在字符串表面滑动的窗口，所以叫滑动窗口。

2.2 窗口的左边界为什么会一直向右

理解滑窗，最重要的是想明白一个问题：left指针为什么可以放心地向右移动，而不用担心漏掉正确答案？

这背后依赖一个单调性假设。以“无重复字符”为例，对于固定右端点right，窗口[left, right]合法时，任何更靠右的left（比如left+1）形成的窗口也一定合法，因为窗口变小了，最多只会丢掉字符，不会凭空产生重复。反过来说，窗口[left, right]非法时，任何更靠左的端点（比如left-1）形成的窗口也一定非法，因为窗口变大了，已经存在的重复字符依旧存在。

这个性质太重要了。它保证了我们不需要回退right去枚举所有窗口，只需要在right固定的情况下，把left一直推到“刚好合法”的位置，此时窗口长度就是当前right下的最大合法长度。left永远不会向左回退，right也永不回头，两个指针总共移动O(n)次，线性复杂度就是这么来的。

我个人更习惯把这个性质叫“窗口条件的单调性”。判断一道题能不能用滑窗，先别急着背模板，先问自己一句：窗口扩大时，条件是不是只会变差？窗口缩小时，条件是不是只会变好？如果答案都是肯定的，滑窗基本可行；如果窗口扩大时条件可能变好也可能变差，那说明存在负向因素，滑窗大概率要翻车。

2.3 三个关键前提，缺一个都别硬套

第一，窗口维护的信息要能随着左右指针移动快速更新。比如字符集合、频次数组、窗口和，这些可以在O(1)时间内增减，如果用滑动窗口维护一个有序数据结构，复杂度就上去了。

第二，题目要的是连续子串或子数组。这是滑窗天生的限制，窗口[left, right]表达的就是连续区间。如果题目要求不连续的子序列，滑窗无从谈起。

第三，条件随窗口伸缩单调变化，也就是2.2节说的性质。这个点最容易被忽略。很多题——尤其是数组里有负数、或者条件是“恰好等于某个目标值”的场景——窗口扩大后满足条件的情况可能从“不满足”跳成“满足”再跳回“不满足”，这时候right往右走没有依据，left往右收也没有依据，整个滑窗就是沙滩上的城堡。

下面四道题，前三道满足这三个前提，第四道不满足，我会在对应章节把对比讲明白。

3. 第3题：无重复字符的最长子串，先写集合版还是先写跳跃版

3.1 集合版代码：最不容易写错的第一版

第3题是很多人的滑窗入门题，我先给出我最推荐的写法，也就是用集合维护窗口字符。每个right位置的字符ch加入窗口前，如果窗口里已经有ch，就一直移出s[left]并让left++，直到ch不再重复，然后加入ch，更新最大长度。

def lengthOfLongestSubstring(s: str) -> int: window = set() left = 0 ans = 0 for right, ch in enumerate(s): while ch in window: window.remove(s[left]) left += 1 window.add(ch) ans = max(ans, right - left + 1) return ans

这个写法的好处是逻辑直白：窗口里是哪些字符一目了然，left收缩的依据也直接写在while条件里。空字符串的情况不需要单独处理，循环不进入，ans天然是0。我在面试里如果能想到这个版本，会先把它写出来，保证正确性，再谈怎么优化。

3.2 跳跃版代码：left直接跳，但小心回退

集合版的left是一个字符一个字符向外挪的。有些时候其实可以跳得更快：比如窗口里出现了重复字符ch，那么新的left可以直接跳到上一次ch出现位置的后一个位置，因为窗口里[left, 上一次ch出现位置]这一整段都不可能再作为答案的起点，它们都要移动到最后一次ch出现位置之后。

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

这个版本最值得讲的一个坑是：为什么是left = max(left, last[ch] + 1)，而不是直接left = last[ch] + 1？因为last[ch]保存的是ch“历史最后一次出现的位置”，这个位置可能出现在当前left的左边。比如字符串"abba"，right遍历到最后一个'a'时，last['a']是0，当前left已经因为中间的'b'移动到了2，如果直接赋值left = last['a'] + 1，left会从2退回1，窗口范围就错了。用max保证left只往右走，不会回退。

面试时如果你写了跳跃版，面试官大概率会拿这个点追问。能答清楚“为什么取max”，比背会这段代码更有价值。

3.3 两个版本的取舍和复杂度

两个版本时间复杂度都是O(n)。集合版最坏情况下每个字符会被加入一次、移出一次，总体仍然是O(n)，但因为窗口内的字符要真正执行remove操作，常数略大。跳跃版空间上用的是哈希表而不是集合，常数小一些，但出错概率更高，尤其是忘记max保护时。

如果是笔试或在线提交，我会写集合版，因为它对错误更宽容。如果是在面试现场，我会先给出集合版，然后主动说“这个还可以用哈希表跳跃优化”，把代码演进给面试官看。这比一上来就写跳跃版更稳，也更能展示你理解两种写法的差异。

4. 第438题：固定窗口的异位词查找，模板化最高的热题

4.1 固定窗口为什么是滑窗家族里最好写的

第438题要求找出字符串s中所有与p互为字母异位词的子串的起始索引。异位词的本质是字母相同、每个字母出现次数相同，只是排列顺序不同。所以这道题的判断标准很明确：窗口长度为len(p)时，窗口内各字符频次是否和p完全一致。

窗口长度固定带来一个巨大的简化：每次滑动，必然进来一个字符、出去一个字符。不需要像第3题那样用while反复收缩left，只需要维护一个固定大小的窗口，然后逐格平移。代码的骨架可以说是滑窗里面最标准的。

我用Counter版本演示一下最清晰的写法：

from collections import Counter def findAnagrams(s: str, p: str) -> list[int]: n, m = len(s), len(p) if n < m: return [] target = Counter(p) window = Counter(s[:m]) ans = [] if window == target: ans.append(0) for i in range(m, n): # 窗口右移：加入新字符s[i]，移除旧字符s[i-m] window[s[i]] += 1 window[s[i - m]] -= 1 if window[s[i - m]] == 0: del window[s[i - m]] if window == target: ans.append(i - m + 1) return ans

这里有个必须说的细节：为什么移除字符后要判断频次是否归零，然后手动del？因为Counter在底层是字典，如果一个字符频次降到0，但你没有删掉它，后续比较window == target时，target里没有该字符，而window里有该字符且值为0，两者并不相等，导致本来合法的窗口被漏判。这是我实际写过踩过的一个坑，第一次提交时莫名其妙少了一个答案，打印出来才发现Counter里留着一堆值为0的键。

4.2 数组计数法：更接近底层、效率更稳

如果你不想用Counter，或者面试环境不强调使用标准库的高级容器，可以用一个长度26的数组手动维护频次。因为这道题只涉及小写字母，字符到索引的映射就是 ord(ch) - ord('a')，比较数组是否相等在Python里天然成立。

def findAnagrams(s: str, p: str) -> list[int]: n, m = len(s), len(p) if n < m: return [] target = [0] * 26 window = [0] * 26 for ch in p: target[ord(ch) - ord('a')] += 1 for ch in s[:m]: window[ord(ch) - ord('a')] += 1 ans = [] if target == window: ans.append(0) for i in range(m, n): window[ord(s[i]) - ord('a')] += 1 window[ord(s[i - m]) - ord('a')] -= 1 if target == window: ans.append(i - m + 1) return ans

数组版的好处是，列表比较的时间复杂度是O(26)，也就是常数级，而且不会出现Counter里值为0残留的问题。缺点是它假设了字符集只有小写字母，如果题目扩展到字母数字或Unicode字符，就需要换成Counter或字典。

4.3 进阶优化：维护差异数，把每次比较降到O(1)

固定窗口解法里，每次滑完都比较一次频次数组，虽然常数小，但面试官可能会问“能不能不比较整个数组”？这时可以维护一个diff变量，表示当前窗口与目标串p有多少个字符的频次不一致。初始时统计窗口与p的差异数；滑动时，只有被影响的旧字符和新字符两个位置的频次发生变化，据此更新diff。diff等于0时，窗口就是一个合法异位词。

这个思路不算难，但写起来容易出bug，因为加入和移除两个操作对diff的影响是相反的。我的建议是：日常刷题或笔试用Counter或数组版足够了，diff优化更多是为了面试交流时展示你对复杂度有概念。如果要在代码里实现diff优化，一定要把“受影响的字符有哪些”列清楚，逐个更新，不要图省事混合写。

5. 第76题：最小覆盖子串，最考验窗口收缩时机的热题

5.1 从异位词到覆盖：窗口长度从固定变成动态

第76题和第438题看起来很像，都是字符串匹配、都是频次计数，但有一个本质差异：第438题的窗口长度固定为len(p)，而第76题要求的是覆盖字符串t的最小窗口。覆盖的含义是，窗口里的字符频次“至少”达到t中各字符的频次，而不是“恰好等于”。窗口可以包含t以外的字符，也可以包含比t所需数量更多的字符，只要“不缺少”就行。

这个“至少”让窗口长度不再固定，你需要一边向右扩right，一边在满足覆盖条件后尝试收缩left，找到刚好覆盖t的最小窗口。收缩却是这道题的精髓：窗口覆盖条件满足后，向右扩展只会让窗口更长，没有意义；此时应该把left向右收，压缩窗口长度，看收到哪里会破坏覆盖条件，破坏之前的所有位置都是候选窗口。

5.2 need字典加need_cnt的配合逻辑

我推荐用一个字典need记录每个字符还缺多少个，同时用一个整数need_cnt记录一共还缺多少个字符。这里格外要注意，need_cnt初始化为len(t)，而不是len(need)，因为t里可能有重复字符。比如t="AABC"，need是{A:2, B:1, C:1}，缺少的字符总数是4，不是3。

每一轮扩展时，如果当前字符ch正好在need里，就把need[ch]减1。减之前如果need[ch]大于0，说明这个字符正好补上了一个缺口，need_cnt减1；如果need[ch]小于等于0，说明窗口里这个字符已经足够甚至过多，多一个并不会让“缺字符总数”变化。

收缩时做的是对称操作。left要向右移动，如果被移出的字符在need里，就把need[left_ch]加1。加之前如果need[left_ch]是0，说明移出后这个字符开始出现缺口，need_cnt加1；如果加之前已经是负数，说明窗口里这个字符多到移出一个也不会缺，need_cnt不变。

def minWindow(s: str, t: str) -> str: if not s or not t or len(s) < len(t): return "" need = {} for ch in t: need[ch] = need.get(ch, 0) + 1 need_cnt = len(t) left = 0 start = 0 min_len = float('inf') for right, ch in enumerate(s): if ch in need: if need[ch] > 0: need_cnt -= 1 need[ch] -= 1 while need_cnt == 0: if right - left + 1 < min_len: min_len = right - left + 1 start = left left_ch = s[left] if left_ch in need: need[left_ch] += 1 if need[left_ch] > 0: need_cnt += 1 left += 1 return "" if min_len == float('inf') else s[start:start + min_len]

这个实现的复杂度是O(n + m)，因为left和right各自最多移动n次，need字典的操作均摊O(1)。

5.3 三个最常见的翻车点

第一个翻车点是更新答案的时机写错。最小窗口一定是在window刚好覆盖t、并且尝试收缩后的窗口里找到的，所以要在while need_cnt == 0循环内部、每次left++之前判断更新。如果把更新写在while外，很可能错过收缩到最紧的那个窗口。

第二个翻车点是扩展时错误地拿“ch是否在t中”作为唯一判断。ch在t里是前提，但真正决定need_cnt是否减1的是need[ch]原来的值是否大于0。我曾经写过一版，看到ch在t里就无脑减need_cnt，结果t里重复字符多的测试用例全部翻车，窗口还没覆盖t，need_cnt已经变成0，后面left一收缩，整个窗口直接崩掉。

第三个翻车点是处理left_ch不在need里的情况。收缩时只判断字典里的字符，窗口里那些无关字符忽略掉继续left++，这时不会影响need_cnt，但必须在while循环里逐字符移动left。很多人把“left_ch in need”的判断写成分支后忘记在不满足时继续移动left，导致死循环或漏掉答案。

5.4 为什么这道题和438题可以共用一个思维

在面试时，如果先被问到第76题，可以把它和第438题放在一起讲：438题是“恰好相等”，所以窗口长度固定，每次滑一步；76题是“至少覆盖”，所以窗口长度可变，right负责扩展，left负责收缩，收缩到刚好破坏覆盖条件为止。两者共同的内核都是频次计数，只是窗口伸缩策略不一样。

把这两道题对照着理解，你会突然发现，所谓最小覆盖子串，本质上就是从所有覆盖t的窗口中找最短的那个，而所有覆盖t的窗口集合，可以通过“left在合法区间内自由移动”来遍历。left每移动一次就是一个新窗口，记录其中最值即可。

6. 第560题：和为K的子数组，为什么在这里滑不动了

6.1 一眼看过去像滑窗，但负数打破了单调性

这道题问的是：给定一个整数数组nums和一个整数k，统计有多少个子数组的和等于k。很多人第一反应是滑窗：维护窗口和，超过k就收缩left，等于k就记一个答案。这个思路在数组元素全为非负时成立，因为窗口和随着right扩展单调不减，超过目标值后只能收缩左侧。

可这道题的数组里可能存在负数。一旦有了负数，窗口向右扩展到某个位置时，和可能是变大也可能是变小；向右收缩left时，和同样可能变大也可能变小。窗口和与窗口边界之间失去了单调对应关系，left该左移还是右移完全无法判断，滑动窗口瞬间失去数学基础。题目也明确说了，nums[i]可以是负数，所以不能用滑窗。

6.2 前缀和哈希：把子数组问题转成两个前缀和的差

子数组nums[j..i]的和等于pre[i+1] - pre[j]，其中pre是前缀和数组。这里pre[k]表示前k个元素的和，pre[0] = 0。要找pre[i+1] - pre[j] = k，也就是pre[j] = pre[i+1] - k。于是问题变成：遍历到每个位置时，之前出现过多少个前缀和等于pre[i+1] - k，这些位置都能和当前前缀配合得到和为k的子数组。

用一个哈希表记录每个前缀和出现的次数即可：

def subarraySum(nums: list[int], k: int) -> int: mp = {0: 1} pre = 0 ans = 0 for num in nums: pre += num if pre - k in mp: ans += mp[pre - k] mp[pre] = mp.get(pre, 0) + 1 return ans

代码只有几行，但有两个细节值得反复强调。第一个细节是，必须在更新mp之前查pre - k。如果你先把自己这个前缀和放进mp，再查，当k等于0时会把自己这一轮的前缀和也算进去，答案凭空多出一堆。第二个细节是mp初始值{0: 1}：前缀和等于0的“位置”要记一次，因为从数组开头到当前元素的整段子数组，对应的pre[j]就是0。

6.3 区间计数和区间最值，解法思路完全不同

把第3题、第76题和第560题摆在一起，你会发现一个规律：前两题求的是最优区间（最长、最短），需要维护一个当前的候选窗口，最后输出一个区间或一个长度；第560题求的是区间个数，需要累计所有符合条件的起点数量。

最优区间问题可以用滑窗，因为你在寻找“一个”窗口，左右指针在单调性约束下可以高效逼近；区间计数问题本质是把“每个终点能和多少个起点配对”统计出来，前缀和哈希是更自然的思路。遇到区间相关题目时，我会先问自己一句：题目要的是最值，还是数量？这个问题的答案直接决定了解题方向。

6.4 同源变体：什么时候可以回到滑窗

如果把第560题改一个条件：数组元素全为非负，求有多少个和为k的子数组。这个问题就可以用滑窗。窗口和超过k或等于k时收缩left，正好等于k时计数，因为全非负时窗口和单调递增，这种计数场景下left能一直右移并维持正确性。

把这道变体作为思考题自己去写一遍，会加深对“单调性决定滑窗是否可用”的理解。我建议在刷完第560题后，顺手做这个变体对比，比多刷十道新题更有价值。

7. 热题100滑窗家族的通用模板与边界自检

7.1 我从这四道题里提炼出来的通用骨架

可变长窗口有一个很稳定的代码骨架，我在做热题100时基本都按这个结构组织：

left = 0 for right in range(n): # 1. 扩展窗口：把 s[right] 纳入窗口 # 2. 更新窗口状态（频次、和、集合等） while 窗口不满足条件: # 3. 收缩窗口：记录候选答案（如果需要） # 4. 移出 s[left] 并更新窗口状态 left += 1 # 5. 收缩完成后，再记录合法窗口的答案（如果需要）

固定长度窗口的骨架更简单，因为不需要while循环收缩，只需要在每次循环里既加又减：

for i in range(m, n): # 纳入 s[i] # 移除 s[i-m] # 判断窗口是否满足条件

7.2 一次提交前必查的边界条件清单

我把这四道题做得多了，总结出一份提交前必查的清单，供你直接抄：

这张表不是背出来的，是我在刷题过程中实际查漏补缺攒出来的，回头看看每一条背后都有一次或多次提交失败的经历。

7.3 热题100里还可以继续延伸的相似题

掌握这四道题之后，热题100里还有一些和滑窗沾边的题目可以顺势刷掉。比如三数之和是双指针但不是窗口滑动，边界条件同样重要；接雨水可以用双指针也可以用单调栈，和滑窗的left-right思路有交叉；最长回文子串用的中心扩展法，也和双指针有关，但逻辑不同。我的经验是：先把这四道题的模板彻底写熟，再去碰这些“长得像但解法不同”的题目，你会发现自己的抽象能力明显提升，看到一个区间问题，能快速判断它属于滑窗还是双指针还是前缀和。

我一直觉得刷热题100最好的方式，不是按题号顺序一路往后推，而是按“算法思维”把题分组。滑动窗口这一组，核心就是“右扩左收+单调性判断”。你把这四道题吃透，后面遇到再新颖的子串子数组题，先想单调性成不成立，再想窗口长度是固定还是可变，最后套模板编码，整个思路就顺了。