拓冰网站定制 
滑动窗口这套东西几乎每个刷算法题的人都会撞上。面试里它是常客刷题平台上的标签也总是挂着它但真正能把滑动窗口讲明白、用明白的文章不多。我见过太多人一看到“滑动窗口”就条件反射套模板结果窗口怎么扩张、怎么收缩、什么时候更新答案全凭感觉写出来的代码跑几个用例就崩。这篇文章我想拿三道经典题目串起整个滑动窗口体系——从字母异位词这种固定窗口到无重复最长子串这种变长窗口再到“将 x 减到 0 的最小操作数”这种必须逆向思考才能联想到滑动窗口的题目。这三道题难度递进正好覆盖了滑动窗口最常见的三种考察姿势。顺便先说明一点这里聊的滑动窗口是算法领域的两指针技巧跟计算机网络里 TCP 流量控制的滑动窗口协议、信号处理里的滑动窗口滤波模型完全是两码事。虽然名字都叫“窗口”但思路和应用场景差别很大。面试的时候如果你能把这两者的区别讲清楚反而是个加分项。文章适合正在准备算法面试的人、刷题刷到滑动窗口标签但总觉得没吃透的人以及想系统整理双指针技巧的人。我会把每一步的“为什么这样做”讲透顺便附上我实际刷题踩过的坑争取让你看完就能自己写出来。1. 滑动窗口到底是什么从一次窗口滑动的物理直觉说起1.1 为什么窗口能“滑”窗口的本质是避免重复计算我第一次学滑动窗口的时候最大的困惑是这玩意不就是两个指针吗为什么非得起个名字叫“窗口”后来我意识到窗口这个比喻的关键在于“覆盖一段连续的空间”。想象你在一串数字上开了一个长度固定的观察窗窗内的元素组成了当前子数组。你要统计某些性质最朴素的办法是把窗内所有元素重新算一遍。但如果你每次只移动一格那窗口里大部分元素都没变只是左边出去一个、右边进来一个。这时候如果你还重新全量计算就是浪费。滑动窗口的核心就是利用上一次计算的结果只处理变化的部分。左边吐出一个元素右边吞进一个元素维护的统计量增量更新。这样一趟走完每个元素最多被“吞”一次、“吐”一次总复杂度是 O(n)。这个思想跟网络里的滑动窗口协议有个共通点——都是让“当前关注的范围”逐步推进而不是反复从头开始。但算法里的滑动窗口更接近一种枚举连续区间的优化手段没有确认、重传那套机制。1.2 所有滑动窗口题都逃不出的两个框架刷了足够多的题之后你会发现滑动窗口其实就两种形态。第一种是固定窗口窗口长度从一开始就确定比如“长度必须为 k 的子数组”“长度必须为 p.length() 的异位词”。这种题你只需要让 right 指针每次前进一格left 也跟着前进一格窗口像履带一样匀速平移。具体代码通常长这样int left 0; for (int right 0; right n; right) { // 把 nums[right] 加入窗口统计 add(nums[right]); // 窗口长度超过 k 时移出 nums[left] 并 left if (right - left 1 k) { remove(nums[left]); left; } // 此时窗口长度一定等于 k if (right - left 1 k) { // 更新答案 } }第二种是变长窗口窗口长度不固定right 负责扩张left 负责在条件不满足时收缩。典型如“无重复字符的最长子串”“最小覆盖子串”。框架长这样int left 0; for (int right 0; right n; right) { // 把 nums[right] 加入窗口 add(nums[right]); // 不满足题目条件时不断收缩 left while (!valid()) { remove(nums[left]); left; } // 此时窗口是合法的更新答案 update(); }这两种框架之间怎么选我一般看题目问的是“固定长度的子串/子数组”还是“最长的/最短的某个子串/子数组”。前者直接上固定窗口后者大概率要变长窗口。当然也有例外比如减零问题窗口长度也是不固定的但它考的重点不是收缩逻辑而是你能不能想到用滑动窗口。选型的时候记住一句话滑动窗口适用于“连续子数组/子串”且有单调性的问题。单调性是指窗口变大时某个状态只朝一个方向变化比如字符频次只增不减、和只增不减。没有单调性滑动窗口就要么用不了要么得配合其他数据结构。2. 第一题字母异位词固定窗口的标准打法2.1 题目与暴力解法的成本分析先看最经典的题目给定字符串 s 和 p找到 s 中所有 p 的字母异位词的子串返回这些子串的起始索引。所谓字母异位词就是字符种类和数量都相同、只是排列顺序不同的字符串。比如 p abc那bca、cab都是它的异位词。我用一个具体例子来说明。s cbaebabacdp abc。肉眼扫一遍cba是异位词起始索引 0bac也是起始索引 6。答案就是 [0, 6]。暴力做法很直观枚举 s 中所有长度等于 p.length() 的子串然后对每个子串做字符频次统计和 p 的频次对比。假设 s 长度是 np 长度是 m枚举的子串有 n - m 1 个每个子串统计频次需要 O(m)总复杂度 O((n-m1) * m)在 n 和 m 都是 10 的 5 次方级别时就彻底跑不动了。这里还有一个隐藏的优化点判断两个字符串互为异位词不需要真的排序。排序的复杂度是 O(m log m)频次统计只需要 O(m)。如果所有字符都是小写字母用长度 26 的数组就够了。这就是我接下来要说的。2.2 用计数数组代替哈希表差别有多大很多人的第一反应是用哈希表 unordered_mapchar, int 来存字符频次。哈希表确实通用但在字符集明确是小写字母的场景里数组的效率远高于哈希表。我说个实际测试感受字符 26 个字母用一个vectorint cnt(26)来统计每次访问下标s[i] - a常数极小。而哈希表每次插入和查找都要计算哈希值可能触发扩容常数大不少。在大数据量下数组版本能快出好几倍。更重要的是数组版本在做“判断当前窗口是否和 p 的频次完全一致”这件事上可以玩出更漂亮的优化。最朴素的做法是每移动一次窗口就比较一遍两个长度为 26 的数组复杂度 O(26 * n)因为 26 是常数所以其实已经堪称 O(n) 了。但真正的高手写法是用一个count变量记录当前窗口中与 p 频次一致的字符个数。只要 count 等于 26就说明窗口内的字符频次和 p 完全一致。2.3 增量更新与 count 优化这步是精髓我直接给出一个非常精简的实现思路。维护两个数组pCount记录 p 的字符频次sCount记录当前窗口的字符频次再用matches记录有多少个字符的频次已经对得上。每次窗口滑动右边新进一个字符 csCount[c]。如果此时sCount[c] pCount[c]说明 c 这个字符的频次刚好对齐了matches 加一。但注意如果sCount[c]从pCount[c] 1变成了pCount[c] 2这个字符从“已经对齐”又变成了“没对齐”matches 应该减一。左边移出的字符同理反向处理。最后如果matches 26当前窗口就是一个合法异位词。我当初写的时候在 matches 的更新逻辑上绕了很久。最容易错的地方是不要以为只要sCount[c]等于pCount[c]就该加 matches。你要先处理好“原本对齐、现在因为加字符变得不对齐”的情况再处理“原本不对齐、现在刚好对齐”的情况。顺序写反结果全是错的。我建议你按这个顺序来先处理 right 进入的字符更新 sCount紧接着检查这个字符是否恰好相等然后更新 matches再处理 left 移出的字符同样先更新 sCount 再更新 matches。不要试图把两种情况压缩成一行可读性差还容易出 bug。2.4 固定窗口最容易被忽略的三个细节第一个细节是窗口初始化。不要在循环里先让 right 走 m 步再开始判断而是从 right 0 开始每次循环先加入一个字符再判断窗口长度是否超过 m。超过就移出左边界。这样窗口就自然保持在 m 的长度逻辑统一。第二个细节是 left 的移动时机的条件。固定窗口里每次 right 移动后都要检查right - left 1 m如果大于 m 就移动 left 并移除一个字符。这个和很容易搞混。如果你希望在窗口长度为 m 时做判断那收缩条件应该是而不是。原因很简单等于 m 的时候窗口刚好符合要求还不该收缩。第三个细节是返回结果的索引。当matches 26时左边界 left 就是当前合法窗口的起点直接加入结果即可。窗口的右边界是 right左边界是 right - m 1但在固定窗口里 left 已经维护了左边界直接用 left 就行。3. 第二题从固定窗口到变长窗口什么时候该收缩3.1 为什么要变长异位词的窗口是定死的但很多问题并不固定异位词那题窗口长度由 p 的长度固定死了所以 left 和 right 同速前进谁都不用让着谁。但现实中的子串问题往往没有给定长度比如“最长无重复子串”“最短覆盖子串”这时候你不可能提前知道窗口应该多长只能动态调整。变长窗口的核心矛盾变成了right 什么时候扩张left 什么时候收缩答案什么时候更新这三件事的顺序决定了你的代码能不能跑对。我举个最典型的例子无重复字符的最长子串。题目要求从字符串中找出一个最长的子串使得其中没有重复字符。比如 s abcabcbb答案是 abc长度 3。我一开始的错解是right 每走一步就把当前字符加入一个 set如果发现 set 里已经有这个字符了就 right 继续走然后等 set 里没有重复时再更新答案。这个思路是错的因为重复字符会让窗口不合法但 right 继续扩张只会让窗口更不合法。正确的做法是right 每走一步先把字符加入窗口如果窗口中出现了重复字符就不断收缩 left直到重复被消除此时窗口一定合法再用窗口长度更新答案。3.2 三件事的顺序不能乱扩张、收缩、更新我之前整理过一套口诀先扩张、再收缩、后更新。扩张就是 right 加入新元素收缩是 while 不满足条件时移出 left 指向的元素更新是在窗口满足条件后记录答案。为什么更新放在最后因为在变长窗口里窗口合法的状态是在收缩之后才确定的。如果你在收缩之前就更新答案拿到的可能是一个非法窗口的长度。反过来说如果你要求的是“最小覆盖子串”这种找最短合法窗口的题更新也必须放在收缩之后因为收缩之后窗口可能更短用更短的窗口更新答案才是对的。这里有一个很多人没想明白的点收缩到什么时候结束答案是收缩到“刚刚不满足约束条件”之后再收缩一步还是收缩到“刚好满足约束条件”为止以无重复子串为例约束条件是窗口内没有重复字符。那收缩到刚好没有重复字符时窗口就是合法的。所以 while 循环的条件一般是“存在重复字符”循环体里不断移出 left直到重复字符被全部赶出去。判断是否存在重复字符可以用一个vectorint freq(128)来记录 ASCII 频次每次加入字符时 freq 自增如果 freq 大于 1 就说明有重复。这样收缩条件是while (freq[s[right]] 1)非常直观。3.3 无重复最长子串的完整推演我们拿 s abcabcbb 完整走一遍帮你把机制刻进脑子里。初始 left 0, right 0freq 全为 0答案 ans 0。right 0加入 afreq[a] 1。窗口 a 无重复长度为 1ans 1。right 1加入 b。窗口 ab 无重复长度 2ans 2。right 2加入 c。窗口 abc 无重复长度 3ans 3。right 3加入 afreq[a] 变成 2有重复。进入 while 循环移除 s[left] 即 aleft 变 1。此时 freq[a] 回到 1循环结束。窗口变成 bca长度 3ans 保持 3。right 4加入 bfreq[b] 变成 2。收缩移除 s[1] bleft 变 2此时窗口是 cab长度 3。right 5加入 cfreq[c] 变成 2。收缩移除 s[2] cleft 变 3窗口是 abc长度 3。right 6加入 bfreq[b] 变成 2。收缩移除 s[3] afreq[a] 变 1但 freq[b] 还是 2继续收缩移除 s[4] bfreq[b] 变 1left 变 5窗口是 cb长度 2ans 仍为 3。right 7加入 bfreq[b] 变成 2。收缩移除 s[5] cleft 变 6移除 s[6] bfreq[b] 变 1left 变 7窗口是 b长度 1。最终答案 3。看到没有这个过程中 left 不是匀速前进的而是根据冲突情况跳跃式收缩。这正是变长窗口和固定窗口最大的不同——固定窗口的 left 是靠条件if控制的变长窗口的 left 是靠while控制的。3.4 变长窗口的收缩条件怎么确定单调性分析我发现很多人卡在“不知道 while 条件怎么写”上。这里我分享一个方法先想清楚窗口什么时候是合法的然后 while 条件就是“不合法”。比如最小覆盖子串问题窗口合法当且仅当窗口内包含了 t 的所有字符。那“不合法”就是“还有某个 t 中的字符没被包含”。维护一个need计数变量当 need 0 时不合法收缩 left当 need 减到 0 时合法更新答案。一旦收缩过头导致 need 变大循环自然停止。这个思路本质上依赖窗口的单调性right 扩张会让窗口越来越“满足”条件left 收缩会让窗口越来越“不满足”条件。如果题目不具备这种单调性滑动窗口就不适用了。比如你要找的窗口同时满足两个互相矛盾的指标left 收缩可能会先让指标 A 变不合法再让指标 B 变合法那 while 循环就没法收敛。4. 第三题减零问题滑动窗口最容易被忽略的逆向思维4.1 题目描述与一开始的错误想法“将 x 减到 0 的最小操作数”是一道非常有意思的题。题目是这样的给定一个整数数组 nums 和一个整数 x你每次操作可以从数组的最左侧或最右侧移除一个元素然后让 x 减去这个元素的值。问最少需要多少次操作能让 x 恰好变成 0。如果做不到返回 -1。比如 nums [1, 1, 4, 2, 3]x 5。你可以移除左侧 1 和 1再移除右侧 3一共 3 次操作x 变为 0。答案就是 3。我第一次看到这题时第一反应是贪心每次比较左右两端的元素谁小就移谁。但很快我就找到了反例。比如 nums [3, 2, 20, 1, 1, 3]x 10。如果你先移除左侧 3再移除右侧 3这时候 x 还剩 4左右两端是 2 和 1你无论怎么移都无法正好凑出 4。但如果第一次不移 3而是先移除右侧的 3、1、1再移除左侧的 2 和 3加起来正好是 10。贪心根本顾不到这种组合。其实这道题的本质是从数组两端删掉一些元素要求这些元素的和等于 x。这等价于在原数组中保留中间一段连续子数组这段子数组的和等于整个数组的总和减去 x。操作次数最少就等于保留的子数组最长。于是问题从“两端删除”变成了“中间寻找最长连续子数组使其和等于 target total - x”。这就是减零问题的“灵魂”它不让你在两端操作而是让你把注意力转向中间。一旦你完成了这个视角转换滑动窗口就顺理成章了。4.2 逆向转换两端删减变成中间连续子数组为什么可以这样转换因为数组是连续的你在左端删掉若干元素、在右端删掉若干元素之后剩下的部分在数组中间而且一定是连续的一段。反过来也一样只要中间连续一段的和等于 total - x那么两端剩余元素的和自然就是 x操作次数就是两端元素的个数。所以原问题就变成了找最长的中间连续子数组使它的和为 total - x。设这个子数组长度为 maxLen答案就是 n - maxLen。如果 total - x 等于 0说明整个数组的元素加起来刚好等于 x你只需要把所有元素都移除答案就是 n。如果 total - x 小于 0说明所有元素加起来都不够 x直接返回 -1。这两个边界条件要提前处理。我见过有人在这个转换上卡了很久因为题目名字叫“减零”脑子很容易被“减”字带偏一直在想怎么从左从右减。换个角度想你其实不是要“减到 0”而是要“从中找出一段和固定的连续区间”难度瞬间就下来了。4.3 具体实现步骤与剩余长度计算接下来是实现。因为是找“和正好等于 target”的最长连续子数组数组元素全是正数或非负数所以窗口和具备单调性right 扩张时窗口和只会变大left 收缩时窗口和只会变小。这就完全符合滑动窗口的使用前提。实现步骤计算数组总和 total。如果 total x直接返回 n。令 target total - x。初始化 left 0windowSum 0maxLen -1。遍历 right 从 0 到 n - 1windowSum nums[right]当 windowSum target 时windowSum - nums[left]left如果 windowSum targetmaxLen max(maxLen, right - left 1)。循环结束后如果 maxLen 还是 -1说明找不到返回 -1否则返回 n - maxLen。这里我踩过一个坑maxLen 的初始值我一开始设的是 0结果当 target 正好等于 0 时空子数组的长度就是 0也能对应合法答案。但题目要求至少需要一次操作才能减少 x如果 x 本身是 0答案应该是 0 而不是 n。所以我在开头要先判断 x 0 的情况那么后面 maxLen 0 的语义就变得模糊了。稳妥的做法是把 maxLen 初始化为 -1找不到时返回 -1找到合法子数组后才更新。4.4 为什么说“减零”会卡人正向贪心不可行的原因再深入聊聊为什么这题容易卡人。滑动窗口本身并不复杂但很多人的思维被题目描述里的“每次可以从左或者右移除”锁死了一直在模拟两端删除的过程。模拟也没有错但状态空间是指数级的因为你每一步都有左右两个选择不可能枚举完。贪心之所以不可行是因为你无法通过局部最优判断下一步应该删左边还是右边。删掉较小的值可能会破坏掉后面凑数的可能性删掉较大的值又可能让 x 提前变成负数。这就是组合优化里典型的“无后效性缺失”必须靠全局视角的等价转换来解决。我把这三题的难度递进总结一下异位词考的是固定窗口的细节处理无重复字符子串考的是变长窗口的收缩时机减零问题考的是能否想到把问题转换成滑动窗口。前两题是“给你一道题你要会写”第三题是“给你一道题你得先发现它能滑动窗口”。这种从模板套用到思路迁移的跨越才是面试真正想考察的东西。5. 实操现场三道题的完整代码与边界条件处理5.1 异位词完整实现C 版 Python 版我先把字母异位词这道题的完整代码贴出来。C 版本的 matches 优化写法如下class Solution { public: vectorint findAnagrams(string s, string p) { vectorint res; int n s.size(), m p.size(); if (n m) return res; vectorint pCount(26, 0), sCount(26, 0); for (char c : p) pCount[c - a]; int matches 0; for (int i 0; i 26; i) { if (pCount[i] sCount[i]) matches; } int left 0; for (int right 0; right n; right) { int idx s[right] - a; sCount[idx]; if (sCount[idx] pCount[idx]) { matches; } else if (sCount[idx] pCount[idx] 1) { matches--; } if (right - left 1 m) { int leftIdx s[left] - a; sCount[leftIdx]--; if (sCount[leftIdx] pCount[leftIdx]) { matches; } else if (sCount[leftIdx] pCount[leftIdx] - 1) { matches--; } left; } if (matches 26) { res.push_back(left); } } return res; } };这段代码里最值得注意的就是matches的增减逻辑。新加入字符后如果频次从 pCount 下面的值刚刚追上 pCountmatches 加一如果频次从刚好等于 pCount 变成比 pCount 多 1说明这个字符从“对齐”变成了“多出来”matches 要减一。左边移除时对称处理但注意移除时频次下降所以判断的是从 pCount 降到 pCount - 1 时 matches 减一从 pCount - 1 刚刚回到 pCount 时 matches 加一。Python 版用 collections.Counter 可以写得很短但为了性能我还是建议用列表加手动维护 match 的方式class Solution: def findAnagrams(self, s: str, p: str) - List[int]: n, m len(s), len(p) if n m: return [] p_count [0] * 26 s_count [0] * 26 for ch in p: p_count[ord(ch) - ord(a)] 1 matches sum(1 for i in range(26) if p_count[i] s_count[i]) res [] left 0 for right in range(n): idx ord(s[right]) - ord(a) s_count[idx] 1 if s_count[idx] p_count[idx]: matches 1 elif s_count[idx] p_count[idx] 1: matches - 1 if right - left 1 m: left_idx ord(s[left]) - ord(a) s_count[left_idx] - 1 if s_count[left_idx] p_count[left_idx]: matches 1 elif s_count[left_idx] p_count[left_idx] - 1: matches - 1 left 1 if matches 26: res.append(left) return res如果你在笔试环境里时间紧张也可以用每次全量比较两个长度为 26 的数组的写法代码更短if s_count p_count: res.append(left)Python 里列表可以直接比较C 里vectorint也支持运算符。但这种写法每次窗口滑动都要比较 26 次虽然 26 是常数但在极端大数据量下还是会慢一些。matches 优化的本质是把“全量比较”降为“局部增量更新”这才是滑动窗口的精髓。5.2 变长窗口完整实现无重复字符的最长子串C 版class Solution { public: int lengthOfLongestSubstring(string s) { vectorint freq(128, 0); int left 0, ans 0; for (int right 0; right s.size(); right) { freq[s[right]]; while (freq[s[right]] 1) { freq[s[left]]--; left; } ans max(ans, right - left 1); } return ans; } };注意这里freq的大小是 128覆盖 ASCII 字符集。如果你只考虑小写字母用 26 也可以但为了稳妥起见我直接开到 128省得处理一些特殊字符时越界。Python 版class Solution: def lengthOfLongestSubstring(self, s: str) - int: freq {} left 0 ans 0 for right, ch in enumerate(s): freq[ch] freq.get(ch, 0) 1 while freq[ch] 1: freq[s[left]] - 1 left 1 ans max(ans, right - left 1) return ans这个 while 循环的条件写作freq[s[right]] 1含义是“当前新加入的字符产生了重复”。收缩时不断移除 left 字符直到这个重复字符的频次降为 1。这个条件设计得非常巧妙它只需要关注新加入的字符是否重复而不需要去扫描整个窗口确认有没有别的重复。因为如果之前窗口没有重复字符新加入一个字符后唯一可能产生重复的就是这个新字符。5.3 减零问题完整实现C 版class Solution { public: int minOperations(vectorint nums, int x) { int n nums.size(); int total 0; for (int num : nums) total num; if (total x) return n; int target total - x; int left 0, windowSum 0, maxLen -1; for (int right 0; right n; right) { windowSum nums[right]; while (windowSum target left right) { windowSum - nums[left]; left; } if (windowSum target) { maxLen max(maxLen, right - left 1); } } return maxLen -1 ? -1 : n - maxLen; } };Python 版class Solution: def minOperations(self, nums: List[int], x: int) - int: n len(nums) total sum(nums) if total x: return n target total - x left 0 window_sum 0 max_len -1 for right in range(n): window_sum nums[right] while window_sum target and left right: window_sum - nums[left] left 1 if window_sum target: max_len max(max_len, right - left 1) return -1 if max_len -1 else n - max_len这里while (windowSum target left right)中的left right是为了防止窗口收缩到空之后 left 继续越界。实际上当 left 超过 right 时窗口为空windowSum 应该是 0循环自然会停止。但有这个条件更安全。5.4 时间与空间复杂度汇总题目时间复杂度空间复杂度核心技巧找到字符串中所有字母异位词O(n)O(1)26 长度数组固定窗口、matches 增量更新无重复字符的最长子串O(n)O(1)128 长度数组变长窗口、收缩条件将 x 减到 0 的最小操作数O(n)O(1)逆向转换、找最长子数组你可能注意到三题的空间复杂度都是 O(1)因为字符集大小固定。如果字符集不固定比如输入是任意 Unicode 字符那就要用哈希表空间复杂度变成 O(字符种类数)。6. 常见问题与排查技巧实录6.1 窗口滑着滑着就死循环了死循环最常见的原因是收缩时 left 没有递增。我见过有人写出这样的代码while (windowSum target) { windowSum - nums[left]; // 忘了 left; }没有 leftleft 永远指向同一个元素windowSum 减一次之后就不会再变了while 条件永远为 true直接卡死。排查这种问题最快的办法是在循环体里加一行打印把 left、right、windowSum 全部打出来一眼就能看到 left 是否在移动。另一个死循环来源是收缩条件写成了比如无重复子串里用while (freq[s[right]] 1)。这会导致窗口里任何一个字符存在就触发收缩最后窗口永远为空ans 永远为 0。这种 bug 比较隐蔽因为代码能跑完只是答案不对。6.2 边界差一left、right 到底取不取Windows 的 left 和 right 都是闭区间的也就是说窗口包含 left 和 right 指向的元素。这个约定一定要在一开始就明确不然后面的长度计算全是错的。窗口长度的公式是right - left 1。如果 right 2left 0窗口包含下标 0、1、2 三个元素长度是 3。固定窗口收缩条件用if (right - left 1 k)意思是当窗口长度超过 k 时收缩。如果你写成窗口长度为 k 时就收缩了右边界刚进来一个元素就被移出去窗口永远凑不满 k 个元素。我建议你在写代码前先在注释里写下约定“窗口为 [left, right] 闭区间”。养成这个习惯之后边界条件基本不会错。6.3 计数数组出现负数计数数组出现负数一般是移除元素的逻辑写错了或者 left 移动的时机不对。比如你在加入元素之前就移除了一个元素此时 left 指向的元素未必还在窗口里重复移除就会导致频次变成负数。还有一种情况是窗口收缩时没有先更新频次再移动 left而是先移动 left 再更新频次。这会导致移除的是 left 移动之后的新窗口里的元素而不是原来的元素。我建议所有移除操作都遵循一个模板先用频次数组把nums[left]减掉再执行 left。顺序不能反否则 left 已经指向下一个元素了你减的可能不是真正要移出的那个。6.4 减零问题中的特殊边界target 等于 0减零问题里有一个边界很多人会踩当 x 正好等于数组总和时target 0你需要移除所有元素答案是 n。我在代码里单独处理了这个情况。如果不做这个特判你有两个选择一是把 maxLen 初始化为 0这样 target 0 时空窗口长度 0 会被当作合法答案最后返回 n - 0 n。但这会引入另一个问题如果 target 不等于 0 且没有合法子数组maxLen 保持 0返回值是 n这显然是错的。所以需要用一个标志位来区分“找到了空窗口”和“没找到任何窗口”。我的习惯是用 maxLen -1 表示没找到用单独判断total x处理特殊情况。这样逻辑最清晰不容易误判。6.5 高频自查清单刷题时遇到滑动窗口我建议按照下面这个清单逐个检查题目是否要求连续子数组/子串不是连续区间滑动窗口大概率不适用。窗口状态是否具备单调性right 扩张时状态单向变化left 收缩时状态反向变化。窗口是固定长度还是变长固定长度用 if 收缩变长长度用 while 收缩。收缩条件写的是“不合法”而不是“合法”吗while 循环里应该写不合法条件。更新答案的位置对吗固定窗口在窗口长度满足后更新变长窗口在收缩完成后更新。边界条件处理了吗比如空输入、窗口长度超过数组长度、target 为负数等。我把这个清单保存成一个笔记每次刷题前过一遍能减少大量低级错误。做算法题这件事刷得多不如总结得透。滑动窗口这套技巧我前前后后刷了不下四十道最后发现核心就是两件事窗口怎么维护答案怎么更新。异位词、无重复子串、减零问题这三道题恰好把固定窗口、变长窗口和逆向思维三种考法串成了一条线。你把这三道题彻底吃透再去刷其他滑动窗口标签的题目会发现大部分都是它们的变体。最后分享一个我自己的小习惯每次写滑动窗口代码前我会在纸上手写一遍窗口从空到满、再到收缩的全过程把 left、right 的每一步变化都写出来。写完之后再动手敲代码正确率会高很多。这个过程就像是在心里模拟一次 TCP 滑动窗口的传输过程——虽然算法题和网络协议应用场合不同但“通过指针维护一个动态关注区间”的直觉是相通的。下次你遇到一道看起来跟滑动窗口八竿子打不着的题不妨先问一句能不能把它转换成连续子数组的问题也许答案就藏在窗口里。 滑动窗口算法详解：三道经典题吃透固定窗口、变长窗口与逆向思维
滑动窗口这套东西几乎每个刷算法题的人都会撞上。面试里它是常客刷题平台上的标签也总是挂着它但真正能把滑动窗口讲明白、用明白的文章不多。我见过太多人一看到“滑动窗口”就条件反射套模板结果窗口怎么扩张、怎么收缩、什么时候更新答案全凭感觉写出来的代码跑几个用例就崩。这篇文章我想拿三道经典题目串起整个滑动窗口体系——从字母异位词这种固定窗口到无重复最长子串这种变长窗口再到“将 x 减到 0 的最小操作数”这种必须逆向思考才能联想到滑动窗口的题目。这三道题难度递进正好覆盖了滑动窗口最常见的三种考察姿势。顺便先说明一点这里聊的滑动窗口是算法领域的两指针技巧跟计算机网络里 TCP 流量控制的滑动窗口协议、信号处理里的滑动窗口滤波模型完全是两码事。虽然名字都叫“窗口”但思路和应用场景差别很大。面试的时候如果你能把这两者的区别讲清楚反而是个加分项。文章适合正在准备算法面试的人、刷题刷到滑动窗口标签但总觉得没吃透的人以及想系统整理双指针技巧的人。我会把每一步的“为什么这样做”讲透顺便附上我实际刷题踩过的坑争取让你看完就能自己写出来。1. 滑动窗口到底是什么从一次窗口滑动的物理直觉说起1.1 为什么窗口能“滑”窗口的本质是避免重复计算我第一次学滑动窗口的时候最大的困惑是这玩意不就是两个指针吗为什么非得起个名字叫“窗口”后来我意识到窗口这个比喻的关键在于“覆盖一段连续的空间”。想象你在一串数字上开了一个长度固定的观察窗窗内的元素组成了当前子数组。你要统计某些性质最朴素的办法是把窗内所有元素重新算一遍。但如果你每次只移动一格那窗口里大部分元素都没变只是左边出去一个、右边进来一个。这时候如果你还重新全量计算就是浪费。滑动窗口的核心就是利用上一次计算的结果只处理变化的部分。左边吐出一个元素右边吞进一个元素维护的统计量增量更新。这样一趟走完每个元素最多被“吞”一次、“吐”一次总复杂度是 O(n)。这个思想跟网络里的滑动窗口协议有个共通点——都是让“当前关注的范围”逐步推进而不是反复从头开始。但算法里的滑动窗口更接近一种枚举连续区间的优化手段没有确认、重传那套机制。1.2 所有滑动窗口题都逃不出的两个框架刷了足够多的题之后你会发现滑动窗口其实就两种形态。第一种是固定窗口窗口长度从一开始就确定比如“长度必须为 k 的子数组”“长度必须为 p.length() 的异位词”。这种题你只需要让 right 指针每次前进一格left 也跟着前进一格窗口像履带一样匀速平移。具体代码通常长这样int left 0; for (int right 0; right n; right) { // 把 nums[right] 加入窗口统计 add(nums[right]); // 窗口长度超过 k 时移出 nums[left] 并 left if (right - left 1 k) { remove(nums[left]); left; } // 此时窗口长度一定等于 k if (right - left 1 k) { // 更新答案 } }第二种是变长窗口窗口长度不固定right 负责扩张left 负责在条件不满足时收缩。典型如“无重复字符的最长子串”“最小覆盖子串”。框架长这样int left 0; for (int right 0; right n; right) { // 把 nums[right] 加入窗口 add(nums[right]); // 不满足题目条件时不断收缩 left while (!valid()) { remove(nums[left]); left; } // 此时窗口是合法的更新答案 update(); }这两种框架之间怎么选我一般看题目问的是“固定长度的子串/子数组”还是“最长的/最短的某个子串/子数组”。前者直接上固定窗口后者大概率要变长窗口。当然也有例外比如减零问题窗口长度也是不固定的但它考的重点不是收缩逻辑而是你能不能想到用滑动窗口。选型的时候记住一句话滑动窗口适用于“连续子数组/子串”且有单调性的问题。单调性是指窗口变大时某个状态只朝一个方向变化比如字符频次只增不减、和只增不减。没有单调性滑动窗口就要么用不了要么得配合其他数据结构。2. 第一题字母异位词固定窗口的标准打法2.1 题目与暴力解法的成本分析先看最经典的题目给定字符串 s 和 p找到 s 中所有 p 的字母异位词的子串返回这些子串的起始索引。所谓字母异位词就是字符种类和数量都相同、只是排列顺序不同的字符串。比如 p abc那bca、cab都是它的异位词。我用一个具体例子来说明。s cbaebabacdp abc。肉眼扫一遍cba是异位词起始索引 0bac也是起始索引 6。答案就是 [0, 6]。暴力做法很直观枚举 s 中所有长度等于 p.length() 的子串然后对每个子串做字符频次统计和 p 的频次对比。假设 s 长度是 np 长度是 m枚举的子串有 n - m 1 个每个子串统计频次需要 O(m)总复杂度 O((n-m1) * m)在 n 和 m 都是 10 的 5 次方级别时就彻底跑不动了。这里还有一个隐藏的优化点判断两个字符串互为异位词不需要真的排序。排序的复杂度是 O(m log m)频次统计只需要 O(m)。如果所有字符都是小写字母用长度 26 的数组就够了。这就是我接下来要说的。2.2 用计数数组代替哈希表差别有多大很多人的第一反应是用哈希表 unordered_mapchar, int 来存字符频次。哈希表确实通用但在字符集明确是小写字母的场景里数组的效率远高于哈希表。我说个实际测试感受字符 26 个字母用一个vectorint cnt(26)来统计每次访问下标s[i] - a常数极小。而哈希表每次插入和查找都要计算哈希值可能触发扩容常数大不少。在大数据量下数组版本能快出好几倍。更重要的是数组版本在做“判断当前窗口是否和 p 的频次完全一致”这件事上可以玩出更漂亮的优化。最朴素的做法是每移动一次窗口就比较一遍两个长度为 26 的数组复杂度 O(26 * n)因为 26 是常数所以其实已经堪称 O(n) 了。但真正的高手写法是用一个count变量记录当前窗口中与 p 频次一致的字符个数。只要 count 等于 26就说明窗口内的字符频次和 p 完全一致。2.3 增量更新与 count 优化这步是精髓我直接给出一个非常精简的实现思路。维护两个数组pCount记录 p 的字符频次sCount记录当前窗口的字符频次再用matches记录有多少个字符的频次已经对得上。每次窗口滑动右边新进一个字符 csCount[c]。如果此时sCount[c] pCount[c]说明 c 这个字符的频次刚好对齐了matches 加一。但注意如果sCount[c]从pCount[c] 1变成了pCount[c] 2这个字符从“已经对齐”又变成了“没对齐”matches 应该减一。左边移出的字符同理反向处理。最后如果matches 26当前窗口就是一个合法异位词。我当初写的时候在 matches 的更新逻辑上绕了很久。最容易错的地方是不要以为只要sCount[c]等于pCount[c]就该加 matches。你要先处理好“原本对齐、现在因为加字符变得不对齐”的情况再处理“原本不对齐、现在刚好对齐”的情况。顺序写反结果全是错的。我建议你按这个顺序来先处理 right 进入的字符更新 sCount紧接着检查这个字符是否恰好相等然后更新 matches再处理 left 移出的字符同样先更新 sCount 再更新 matches。不要试图把两种情况压缩成一行可读性差还容易出 bug。2.4 固定窗口最容易被忽略的三个细节第一个细节是窗口初始化。不要在循环里先让 right 走 m 步再开始判断而是从 right 0 开始每次循环先加入一个字符再判断窗口长度是否超过 m。超过就移出左边界。这样窗口就自然保持在 m 的长度逻辑统一。第二个细节是 left 的移动时机的条件。固定窗口里每次 right 移动后都要检查right - left 1 m如果大于 m 就移动 left 并移除一个字符。这个和很容易搞混。如果你希望在窗口长度为 m 时做判断那收缩条件应该是而不是。原因很简单等于 m 的时候窗口刚好符合要求还不该收缩。第三个细节是返回结果的索引。当matches 26时左边界 left 就是当前合法窗口的起点直接加入结果即可。窗口的右边界是 right左边界是 right - m 1但在固定窗口里 left 已经维护了左边界直接用 left 就行。3. 第二题从固定窗口到变长窗口什么时候该收缩3.1 为什么要变长异位词的窗口是定死的但很多问题并不固定异位词那题窗口长度由 p 的长度固定死了所以 left 和 right 同速前进谁都不用让着谁。但现实中的子串问题往往没有给定长度比如“最长无重复子串”“最短覆盖子串”这时候你不可能提前知道窗口应该多长只能动态调整。变长窗口的核心矛盾变成了right 什么时候扩张left 什么时候收缩答案什么时候更新这三件事的顺序决定了你的代码能不能跑对。我举个最典型的例子无重复字符的最长子串。题目要求从字符串中找出一个最长的子串使得其中没有重复字符。比如 s abcabcbb答案是 abc长度 3。我一开始的错解是right 每走一步就把当前字符加入一个 set如果发现 set 里已经有这个字符了就 right 继续走然后等 set 里没有重复时再更新答案。这个思路是错的因为重复字符会让窗口不合法但 right 继续扩张只会让窗口更不合法。正确的做法是right 每走一步先把字符加入窗口如果窗口中出现了重复字符就不断收缩 left直到重复被消除此时窗口一定合法再用窗口长度更新答案。3.2 三件事的顺序不能乱扩张、收缩、更新我之前整理过一套口诀先扩张、再收缩、后更新。扩张就是 right 加入新元素收缩是 while 不满足条件时移出 left 指向的元素更新是在窗口满足条件后记录答案。为什么更新放在最后因为在变长窗口里窗口合法的状态是在收缩之后才确定的。如果你在收缩之前就更新答案拿到的可能是一个非法窗口的长度。反过来说如果你要求的是“最小覆盖子串”这种找最短合法窗口的题更新也必须放在收缩之后因为收缩之后窗口可能更短用更短的窗口更新答案才是对的。这里有一个很多人没想明白的点收缩到什么时候结束答案是收缩到“刚刚不满足约束条件”之后再收缩一步还是收缩到“刚好满足约束条件”为止以无重复子串为例约束条件是窗口内没有重复字符。那收缩到刚好没有重复字符时窗口就是合法的。所以 while 循环的条件一般是“存在重复字符”循环体里不断移出 left直到重复字符被全部赶出去。判断是否存在重复字符可以用一个vectorint freq(128)来记录 ASCII 频次每次加入字符时 freq 自增如果 freq 大于 1 就说明有重复。这样收缩条件是while (freq[s[right]] 1)非常直观。3.3 无重复最长子串的完整推演我们拿 s abcabcbb 完整走一遍帮你把机制刻进脑子里。初始 left 0, right 0freq 全为 0答案 ans 0。right 0加入 afreq[a] 1。窗口 a 无重复长度为 1ans 1。right 1加入 b。窗口 ab 无重复长度 2ans 2。right 2加入 c。窗口 abc 无重复长度 3ans 3。right 3加入 afreq[a] 变成 2有重复。进入 while 循环移除 s[left] 即 aleft 变 1。此时 freq[a] 回到 1循环结束。窗口变成 bca长度 3ans 保持 3。right 4加入 bfreq[b] 变成 2。收缩移除 s[1] bleft 变 2此时窗口是 cab长度 3。right 5加入 cfreq[c] 变成 2。收缩移除 s[2] cleft 变 3窗口是 abc长度 3。right 6加入 bfreq[b] 变成 2。收缩移除 s[3] afreq[a] 变 1但 freq[b] 还是 2继续收缩移除 s[4] bfreq[b] 变 1left 变 5窗口是 cb长度 2ans 仍为 3。right 7加入 bfreq[b] 变成 2。收缩移除 s[5] cleft 变 6移除 s[6] bfreq[b] 变 1left 变 7窗口是 b长度 1。最终答案 3。看到没有这个过程中 left 不是匀速前进的而是根据冲突情况跳跃式收缩。这正是变长窗口和固定窗口最大的不同——固定窗口的 left 是靠条件if控制的变长窗口的 left 是靠while控制的。3.4 变长窗口的收缩条件怎么确定单调性分析我发现很多人卡在“不知道 while 条件怎么写”上。这里我分享一个方法先想清楚窗口什么时候是合法的然后 while 条件就是“不合法”。比如最小覆盖子串问题窗口合法当且仅当窗口内包含了 t 的所有字符。那“不合法”就是“还有某个 t 中的字符没被包含”。维护一个need计数变量当 need 0 时不合法收缩 left当 need 减到 0 时合法更新答案。一旦收缩过头导致 need 变大循环自然停止。这个思路本质上依赖窗口的单调性right 扩张会让窗口越来越“满足”条件left 收缩会让窗口越来越“不满足”条件。如果题目不具备这种单调性滑动窗口就不适用了。比如你要找的窗口同时满足两个互相矛盾的指标left 收缩可能会先让指标 A 变不合法再让指标 B 变合法那 while 循环就没法收敛。4. 第三题减零问题滑动窗口最容易被忽略的逆向思维4.1 题目描述与一开始的错误想法“将 x 减到 0 的最小操作数”是一道非常有意思的题。题目是这样的给定一个整数数组 nums 和一个整数 x你每次操作可以从数组的最左侧或最右侧移除一个元素然后让 x 减去这个元素的值。问最少需要多少次操作能让 x 恰好变成 0。如果做不到返回 -1。比如 nums [1, 1, 4, 2, 3]x 5。你可以移除左侧 1 和 1再移除右侧 3一共 3 次操作x 变为 0。答案就是 3。我第一次看到这题时第一反应是贪心每次比较左右两端的元素谁小就移谁。但很快我就找到了反例。比如 nums [3, 2, 20, 1, 1, 3]x 10。如果你先移除左侧 3再移除右侧 3这时候 x 还剩 4左右两端是 2 和 1你无论怎么移都无法正好凑出 4。但如果第一次不移 3而是先移除右侧的 3、1、1再移除左侧的 2 和 3加起来正好是 10。贪心根本顾不到这种组合。其实这道题的本质是从数组两端删掉一些元素要求这些元素的和等于 x。这等价于在原数组中保留中间一段连续子数组这段子数组的和等于整个数组的总和减去 x。操作次数最少就等于保留的子数组最长。于是问题从“两端删除”变成了“中间寻找最长连续子数组使其和等于 target total - x”。这就是减零问题的“灵魂”它不让你在两端操作而是让你把注意力转向中间。一旦你完成了这个视角转换滑动窗口就顺理成章了。4.2 逆向转换两端删减变成中间连续子数组为什么可以这样转换因为数组是连续的你在左端删掉若干元素、在右端删掉若干元素之后剩下的部分在数组中间而且一定是连续的一段。反过来也一样只要中间连续一段的和等于 total - x那么两端剩余元素的和自然就是 x操作次数就是两端元素的个数。所以原问题就变成了找最长的中间连续子数组使它的和为 total - x。设这个子数组长度为 maxLen答案就是 n - maxLen。如果 total - x 等于 0说明整个数组的元素加起来刚好等于 x你只需要把所有元素都移除答案就是 n。如果 total - x 小于 0说明所有元素加起来都不够 x直接返回 -1。这两个边界条件要提前处理。我见过有人在这个转换上卡了很久因为题目名字叫“减零”脑子很容易被“减”字带偏一直在想怎么从左从右减。换个角度想你其实不是要“减到 0”而是要“从中找出一段和固定的连续区间”难度瞬间就下来了。4.3 具体实现步骤与剩余长度计算接下来是实现。因为是找“和正好等于 target”的最长连续子数组数组元素全是正数或非负数所以窗口和具备单调性right 扩张时窗口和只会变大left 收缩时窗口和只会变小。这就完全符合滑动窗口的使用前提。实现步骤计算数组总和 total。如果 total x直接返回 n。令 target total - x。初始化 left 0windowSum 0maxLen -1。遍历 right 从 0 到 n - 1windowSum nums[right]当 windowSum target 时windowSum - nums[left]left如果 windowSum targetmaxLen max(maxLen, right - left 1)。循环结束后如果 maxLen 还是 -1说明找不到返回 -1否则返回 n - maxLen。这里我踩过一个坑maxLen 的初始值我一开始设的是 0结果当 target 正好等于 0 时空子数组的长度就是 0也能对应合法答案。但题目要求至少需要一次操作才能减少 x如果 x 本身是 0答案应该是 0 而不是 n。所以我在开头要先判断 x 0 的情况那么后面 maxLen 0 的语义就变得模糊了。稳妥的做法是把 maxLen 初始化为 -1找不到时返回 -1找到合法子数组后才更新。4.4 为什么说“减零”会卡人正向贪心不可行的原因再深入聊聊为什么这题容易卡人。滑动窗口本身并不复杂但很多人的思维被题目描述里的“每次可以从左或者右移除”锁死了一直在模拟两端删除的过程。模拟也没有错但状态空间是指数级的因为你每一步都有左右两个选择不可能枚举完。贪心之所以不可行是因为你无法通过局部最优判断下一步应该删左边还是右边。删掉较小的值可能会破坏掉后面凑数的可能性删掉较大的值又可能让 x 提前变成负数。这就是组合优化里典型的“无后效性缺失”必须靠全局视角的等价转换来解决。我把这三题的难度递进总结一下异位词考的是固定窗口的细节处理无重复字符子串考的是变长窗口的收缩时机减零问题考的是能否想到把问题转换成滑动窗口。前两题是“给你一道题你要会写”第三题是“给你一道题你得先发现它能滑动窗口”。这种从模板套用到思路迁移的跨越才是面试真正想考察的东西。5. 实操现场三道题的完整代码与边界条件处理5.1 异位词完整实现C 版 Python 版我先把字母异位词这道题的完整代码贴出来。C 版本的 matches 优化写法如下class Solution { public: vectorint findAnagrams(string s, string p) { vectorint res; int n s.size(), m p.size(); if (n m) return res; vectorint pCount(26, 0), sCount(26, 0); for (char c : p) pCount[c - a]; int matches 0; for (int i 0; i 26; i) { if (pCount[i] sCount[i]) matches; } int left 0; for (int right 0; right n; right) { int idx s[right] - a; sCount[idx]; if (sCount[idx] pCount[idx]) { matches; } else if (sCount[idx] pCount[idx] 1) { matches--; } if (right - left 1 m) { int leftIdx s[left] - a; sCount[leftIdx]--; if (sCount[leftIdx] pCount[leftIdx]) { matches; } else if (sCount[leftIdx] pCount[leftIdx] - 1) { matches--; } left; } if (matches 26) { res.push_back(left); } } return res; } };这段代码里最值得注意的就是matches的增减逻辑。新加入字符后如果频次从 pCount 下面的值刚刚追上 pCountmatches 加一如果频次从刚好等于 pCount 变成比 pCount 多 1说明这个字符从“对齐”变成了“多出来”matches 要减一。左边移除时对称处理但注意移除时频次下降所以判断的是从 pCount 降到 pCount - 1 时 matches 减一从 pCount - 1 刚刚回到 pCount 时 matches 加一。Python 版用 collections.Counter 可以写得很短但为了性能我还是建议用列表加手动维护 match 的方式class Solution: def findAnagrams(self, s: str, p: str) - List[int]: n, m len(s), len(p) if n m: return [] p_count [0] * 26 s_count [0] * 26 for ch in p: p_count[ord(ch) - ord(a)] 1 matches sum(1 for i in range(26) if p_count[i] s_count[i]) res [] left 0 for right in range(n): idx ord(s[right]) - ord(a) s_count[idx] 1 if s_count[idx] p_count[idx]: matches 1 elif s_count[idx] p_count[idx] 1: matches - 1 if right - left 1 m: left_idx ord(s[left]) - ord(a) s_count[left_idx] - 1 if s_count[left_idx] p_count[left_idx]: matches 1 elif s_count[left_idx] p_count[left_idx] - 1: matches - 1 left 1 if matches 26: res.append(left) return res如果你在笔试环境里时间紧张也可以用每次全量比较两个长度为 26 的数组的写法代码更短if s_count p_count: res.append(left)Python 里列表可以直接比较C 里vectorint也支持运算符。但这种写法每次窗口滑动都要比较 26 次虽然 26 是常数但在极端大数据量下还是会慢一些。matches 优化的本质是把“全量比较”降为“局部增量更新”这才是滑动窗口的精髓。5.2 变长窗口完整实现无重复字符的最长子串C 版class Solution { public: int lengthOfLongestSubstring(string s) { vectorint freq(128, 0); int left 0, ans 0; for (int right 0; right s.size(); right) { freq[s[right]]; while (freq[s[right]] 1) { freq[s[left]]--; left; } ans max(ans, right - left 1); } return ans; } };注意这里freq的大小是 128覆盖 ASCII 字符集。如果你只考虑小写字母用 26 也可以但为了稳妥起见我直接开到 128省得处理一些特殊字符时越界。Python 版class Solution: def lengthOfLongestSubstring(self, s: str) - int: freq {} left 0 ans 0 for right, ch in enumerate(s): freq[ch] freq.get(ch, 0) 1 while freq[ch] 1: freq[s[left]] - 1 left 1 ans max(ans, right - left 1) return ans这个 while 循环的条件写作freq[s[right]] 1含义是“当前新加入的字符产生了重复”。收缩时不断移除 left 字符直到这个重复字符的频次降为 1。这个条件设计得非常巧妙它只需要关注新加入的字符是否重复而不需要去扫描整个窗口确认有没有别的重复。因为如果之前窗口没有重复字符新加入一个字符后唯一可能产生重复的就是这个新字符。5.3 减零问题完整实现C 版class Solution { public: int minOperations(vectorint nums, int x) { int n nums.size(); int total 0; for (int num : nums) total num; if (total x) return n; int target total - x; int left 0, windowSum 0, maxLen -1; for (int right 0; right n; right) { windowSum nums[right]; while (windowSum target left right) { windowSum - nums[left]; left; } if (windowSum target) { maxLen max(maxLen, right - left 1); } } return maxLen -1 ? -1 : n - maxLen; } };Python 版class Solution: def minOperations(self, nums: List[int], x: int) - int: n len(nums) total sum(nums) if total x: return n target total - x left 0 window_sum 0 max_len -1 for right in range(n): window_sum nums[right] while window_sum target and left right: window_sum - nums[left] left 1 if window_sum target: max_len max(max_len, right - left 1) return -1 if max_len -1 else n - max_len这里while (windowSum target left right)中的left right是为了防止窗口收缩到空之后 left 继续越界。实际上当 left 超过 right 时窗口为空windowSum 应该是 0循环自然会停止。但有这个条件更安全。5.4 时间与空间复杂度汇总题目时间复杂度空间复杂度核心技巧找到字符串中所有字母异位词O(n)O(1)26 长度数组固定窗口、matches 增量更新无重复字符的最长子串O(n)O(1)128 长度数组变长窗口、收缩条件将 x 减到 0 的最小操作数O(n)O(1)逆向转换、找最长子数组你可能注意到三题的空间复杂度都是 O(1)因为字符集大小固定。如果字符集不固定比如输入是任意 Unicode 字符那就要用哈希表空间复杂度变成 O(字符种类数)。6. 常见问题与排查技巧实录6.1 窗口滑着滑着就死循环了死循环最常见的原因是收缩时 left 没有递增。我见过有人写出这样的代码while (windowSum target) { windowSum - nums[left]; // 忘了 left; }没有 leftleft 永远指向同一个元素windowSum 减一次之后就不会再变了while 条件永远为 true直接卡死。排查这种问题最快的办法是在循环体里加一行打印把 left、right、windowSum 全部打出来一眼就能看到 left 是否在移动。另一个死循环来源是收缩条件写成了比如无重复子串里用while (freq[s[right]] 1)。这会导致窗口里任何一个字符存在就触发收缩最后窗口永远为空ans 永远为 0。这种 bug 比较隐蔽因为代码能跑完只是答案不对。6.2 边界差一left、right 到底取不取Windows 的 left 和 right 都是闭区间的也就是说窗口包含 left 和 right 指向的元素。这个约定一定要在一开始就明确不然后面的长度计算全是错的。窗口长度的公式是right - left 1。如果 right 2left 0窗口包含下标 0、1、2 三个元素长度是 3。固定窗口收缩条件用if (right - left 1 k)意思是当窗口长度超过 k 时收缩。如果你写成窗口长度为 k 时就收缩了右边界刚进来一个元素就被移出去窗口永远凑不满 k 个元素。我建议你在写代码前先在注释里写下约定“窗口为 [left, right] 闭区间”。养成这个习惯之后边界条件基本不会错。6.3 计数数组出现负数计数数组出现负数一般是移除元素的逻辑写错了或者 left 移动的时机不对。比如你在加入元素之前就移除了一个元素此时 left 指向的元素未必还在窗口里重复移除就会导致频次变成负数。还有一种情况是窗口收缩时没有先更新频次再移动 left而是先移动 left 再更新频次。这会导致移除的是 left 移动之后的新窗口里的元素而不是原来的元素。我建议所有移除操作都遵循一个模板先用频次数组把nums[left]减掉再执行 left。顺序不能反否则 left 已经指向下一个元素了你减的可能不是真正要移出的那个。6.4 减零问题中的特殊边界target 等于 0减零问题里有一个边界很多人会踩当 x 正好等于数组总和时target 0你需要移除所有元素答案是 n。我在代码里单独处理了这个情况。如果不做这个特判你有两个选择一是把 maxLen 初始化为 0这样 target 0 时空窗口长度 0 会被当作合法答案最后返回 n - 0 n。但这会引入另一个问题如果 target 不等于 0 且没有合法子数组maxLen 保持 0返回值是 n这显然是错的。所以需要用一个标志位来区分“找到了空窗口”和“没找到任何窗口”。我的习惯是用 maxLen -1 表示没找到用单独判断total x处理特殊情况。这样逻辑最清晰不容易误判。6.5 高频自查清单刷题时遇到滑动窗口我建议按照下面这个清单逐个检查题目是否要求连续子数组/子串不是连续区间滑动窗口大概率不适用。窗口状态是否具备单调性right 扩张时状态单向变化left 收缩时状态反向变化。窗口是固定长度还是变长固定长度用 if 收缩变长长度用 while 收缩。收缩条件写的是“不合法”而不是“合法”吗while 循环里应该写不合法条件。更新答案的位置对吗固定窗口在窗口长度满足后更新变长窗口在收缩完成后更新。边界条件处理了吗比如空输入、窗口长度超过数组长度、target 为负数等。我把这个清单保存成一个笔记每次刷题前过一遍能减少大量低级错误。做算法题这件事刷得多不如总结得透。滑动窗口这套技巧我前前后后刷了不下四十道最后发现核心就是两件事窗口怎么维护答案怎么更新。异位词、无重复子串、减零问题这三道题恰好把固定窗口、变长窗口和逆向思维三种考法串成了一条线。你把这三道题彻底吃透再去刷其他滑动窗口标签的题目会发现大部分都是它们的变体。最后分享一个我自己的小习惯每次写滑动窗口代码前我会在纸上手写一遍窗口从空到满、再到收缩的全过程把 left、right 的每一步变化都写出来。写完之后再动手敲代码正确率会高很多。这个过程就像是在心里模拟一次 TCP 滑动窗口的传输过程——虽然算法题和网络协议应用场合不同但“通过指针维护一个动态关注区间”的直觉是相通的。下次你遇到一道看起来跟滑动窗口八竿子打不着的题不妨先问一句能不能把它转换成连续子数组的问题也许答案就藏在窗口里。