如果你最近在刷算法题滑动窗口这四个字应该没少听。我第一次被它真正搞明白就是被“找到字符串中所有字母异位词”这题逼的。当时暴力解法写起来很简单但一跑大用例就超时怎么优化都觉得别扭。后来刷到“把 x 减到 0 的最小操作数”时又愣了一下这题看起来跟窗口八竿子打不着结果绕来绕去核心还是滑动窗口。所以我打算把这三道经典题放在一起聊从异位词一路聊到减零问题把窗口为什么能省时间、代码怎么写才不容易错、遇到变形怎么一眼认出来一次讲透。今天这篇适合正在准备面试的人也适合已经刷过一些题、但总觉得滑动窗口换个壳就不会写的人。1. 滑动窗口这套模板到底在解决什么问题1.1 从暴力解到窗口思想为什么窗口能省时间先聊个底层问题滑动窗口到底在优化什么拿异位词来说暴力解法是枚举 s 中所有长度为 len(p) 的子串然后挨个判断这个子串是不是 p 的异位词。假设 s 的长度是 np 的长度是 m那枚举的子串数量是 n-m1每个子串如果要排序再比较复杂度就是 O(m log m)整体直接变成 O(nm log m)。就算不排序、改用计数数组每个子串仍要重新统计一遍字符频次复杂度 O(nm)。滑动窗口的思路完全不一样窗口每次只向右移动一格左边吐出一个字符右边吃进一个字符。窗口里的字符频次变化是局部的、增量的而不是重新统计整段内容。这样每个字符最多被加入窗口一次、移出窗口一次总时间复杂度就是 O(n)。这个道理跟“端盘子”很像你要数一桌人吃了多少道菜从头数一遍当然可以但每上一道新菜只记录新增的那一道显然更快。类似的省时间逻辑几乎贯穿所有滑动窗口题目。窗口不是某种花哨的数据结构它本质上是一种增量维护状态的思路让状态的变化跟随指针的移动而不是每次重新计算。1.2 一套模板吃透三种题型定长、变长、最值变体滑动窗口的题目看起来很多但我刷下来发现核心就三种变化。第一种是定长窗口。窗口长度固定比如“长度固定为 len(p) 的异位词子串”右指针每走一步左指针也跟着走一步窗口始终保持固定长度。这种题目的关键是在窗口长度固定后判断当前窗口的内容是否满足条件。第二种是变长窗口求最短合法子串。典型就是最小覆盖子串右指针不断扩展直到窗口内包含了 t 的所有字符然后左指针开始收缩试图找到以当前右指针为结尾的最短覆盖。更新答案的时机在收缩之前因为一旦收缩就可能不再满足覆盖条件。第三种也是变长窗口但求的是最长合法子串。比如减零问题转化后的“寻找和为 target 的最长子数组”右指针扩展窗口和超过 target 后收缩收缩完成后再检查当前窗口是否满足目标值然后更新最大长度。更新答案的时机在收缩之后。很多资料会把滑动窗口统一写成一个模板比如“右指针扩张、while 不满足条件时左指针收缩、收缩后更新答案”。但我个人的体会是模板只能给个大致框架真正的差异恰恰在上面的“更新时机”和“收缩条件”里。这三题刚好把三种形态都覆盖到所以很适合放在一起对比。2. 第一题找到字符串中所有字母异位词定长窗口2.1 题意与解题方向题目是这样的给定两个字符串 s 和 p找到 s 中所有 p 的异位词的子串返回这些子串的起始索引。所谓异位词就是两个字符串包含的字符种类和数量完全相同只是排列顺序不同。比如 p abc那么 bca、cab 都是它的异位词。这个题如果用暴力做相当于把 s 切成一段一段长度为 len(p) 的片段然后验证每个片段和 p 的字符频次是否一致。复杂度高不说切片的起始位置也容易搞乱。用滑动窗口本质上就是维护一个长度始终等于 len(p) 的窗口窗口内是一个长度为 len(p) 的子串然后用一个计数数组记录窗口内每个字母的出现次数和 p 的计数数组做比较。为什么能用计数数组因为题目只关心“字符组成是否相同”不关心顺序。异位词判断不需要排序只需要判断字符频次是否完全一致。只要把 p 的频次数组 need 算出来再拿窗口的频次数组 window 去比对相等就说明当前子串是异位词。2.2 定长窗口代码与过程演示直接上代码我用 Python 写def findAnagrams(s: str, p: str) - List[int]: n, k len(s), len(p) if n k: return [] need [0] * 26 for ch in p: need[ord(ch) - ord(a)] 1 window [0] * 26 res [] left 0 for right in range(n): # 右边界字符进入窗口 window[ord(s[right]) - ord(a)] 1 # 窗口长度超过 k左边界字符移出窗口 if right - left 1 k: window[ord(s[left]) - ord(a)] - 1 left 1 # 窗口长度刚好等于 k且频次完全一致记录起点 if right - left 1 k and window need: res.append(left) return res这段代码的窗口始终是定长的。right 每走一步left 只有在窗口超长时才跟着走所以窗口内的字符数量始终不会超过 k。当窗口长度正好是 k 时判断 window 和 need 是否相等相等就把 left 记进结果。拿一个例子走一遍。s cbaebabacdp abck 3。窗口先走到 cba长度正好 3window 里 a、b、c 各一个need 也是 abc 各一个相等记录起点 0。之后窗口滑动到 baea、b、e 各一个不等于 need不记录。继续滑到 bac 时窗口内是 b、a、c又相等了记录起点 6。最终结果就是 [0, 6]。这里有个小细节为什么窗口超长时用 if 而不是 while因为窗口长度是固定 kright 每次只加一个字符left 也最多只需要移出一个字符就能恢复长度 k所以 if 就够了。如果你写成 while也不会出错但语义上没必要。2.3 为什么用计数数组而不是哈希表很多解法里会用字典来统计字符频次但在这道题里计数数组更合适。因为题目明确说了 s 和 p 只包含小写字母总共就 26 个字符。用长度为 26 的数组比较两个数组是否相等可以直接window needPython 对列表的相等判断是按元素逐个比较速度快代码也简洁。如果用字典需要处理“键不存在”的情况还得写循环逐项比较代码会啰嗦不少。当然如果题目改成包含任意 Unicode 字符计数数组就不现实了那时候再用 defaultdict(int) 或者 Counter。另外有个细节window need这个比较发生在窗口长度刚好等于 k 的时候。这个时机很关键如果写在窗口长度超过 k 之后再比较就可能把长度大于 k 的窗口拿去判断结果自然不对。提示定长窗口的核心是“固定长度 频次比较”。只要窗口长度稳定你可以在不同题目里替换比较逻辑。3. 第二题最小覆盖子串变长窗口3.1 从定长到变长窗口合法那一刻才开始收缩第二题是力扣 76 题最小覆盖子串。题目要求从 s 里找出包含 t 的全部字符的最短子串。注意这里窗口长度不是固定的因为 t 可能很短而 s 里覆盖 t 的子串可能长短不一。这题的关键是判断“窗口什么时候合法”。我的做法是用两张表need 记录 t 中每个字符需要的次数window 记录当前窗口里每个字符出现的次数。另外维护一个 match 变量表示“已经有多少个字符满足了数量要求”。注意是“种类数”而不是“字符总数”。举个例子t AABC那么 A 需要 2 次B、C 各需要 1 次。如果当前窗口里 A 出现 2 次、B 出现 1 次、C 还没出现那 match 是 2因为 A 和 B 这两种字符已经满足了C 还没满足。只有当 A、B、C 这三种字符都满足要求时match 才等于 len(need)窗口才算合法。3.2 匹配计数与收缩逻辑拆解代码框架是这样def minWindow(s: str, t: str) - str: if not s or not t: return need {} for ch in t: need[ch] need.get(ch, 0) 1 window {} match 0 need_cnt len(need) left 0 start 0 min_len float(inf) for right, ch in enumerate(s): window[ch] window.get(ch, 0) 1 if ch in need and window[ch] need[ch]: match 1 while match need_cnt: # 窗口合法尝试更新最短长度 if right - left 1 min_len: min_len right - left 1 start left # 左边界字符移出窗口 d s[left] if d in need and window[d] need[d]: match - 1 window[d] - 1 left 1 return s[start:startmin_len] if min_len ! float(inf) else 这里有几个容易写错的地方。第一个是 match 的增减条件。右边界加入字符时只有当window[ch] need[ch]才 match 加一因为只有“恰好达到目标数量”才说明这个字符从“不满足”变成了“满足”。如果窗口里这个字符数量已经超过需求了match 不应当再加。收缩时同理只有当移出的字符导致window[d]从“刚好等于 need[d]”变成“小于 need[d]”这个字符才从“满足”退回“不满足”match 才减一。如果窗口里这个字符数量多的是少一个也不影响match 不用动。第二个是 while 循环里的执行顺序。先记录当前最短结果再收缩左边界。因为收缩之后窗口可能就不合法了所以必须在收缩前把当前合法窗口的长度记录下来。第三个是窗口字符移出后要把 window[d] 也减掉。很多人会忘记维护这个计数导致判断条件失真。3.3 为什么滑动窗口不会漏掉最优解这题我第一次看的时候总觉得不踏实右指针一直往右移动左指针只在合法时收缩这样会不会把某个潜在的最优解漏掉实际上不会。你可以这样想固定右指针的位置如果当前窗口合法那么左指针能收缩到哪里取决于“保持合法”这个约束。收缩到不能再收缩时你得到的就是“以当前右指针为结尾的最短合法窗口”。全局最短合法子串的右端点一定是某个位置当右指针扫到那个位置时左指针就有机会收缩到最优的左边起点因此全局最优解一定会在某次循环里被记录。这也是滑动窗口能够替代暴力枚举的根本原因它没有跳过任何“右端点”只是在每个右端点上快速找到了对应的最优左端点。注意最小覆盖子串属于“最短合法窗口”类型更新答案要放在收缩之前。这是和第三题最大的区别。4. 第三题减零问题将 x 减到 0 的最小操作数4.1 正面硬做很困难因为每一步都可以从两端选第三题我习惯叫它减零问题对应力扣 1658 题。题目大意是给你一个整数数组 nums 和一个整数 x每次操作你可以移除 nums 最左边或最右边的元素然后从 x 中减去该元素的值。问能否通过若干次操作把 x 恰好减到 0如果能返回最小操作数否则返回 -1。第一眼看到这题很容易陷入模拟的思路每次从左端还是右端拿这是一个二选一的分支暴力搜索就是指数级复杂度。但仔细想一下最后被移除的元素一定是数组左端的一段连续前缀加上右端的一段连续后缀。换句话说数组中剩下的部分是一个连续的子数组它的和等于 nums 总和减去 x。设 total 是 nums 的总和target total - x。那么问题就变成找到一个最长的连续子数组使它的和等于 target。因为中间保留的子数组越长两端的操作数就越少。最终结果就是 len(nums) - max_len其中 max_len 是最长合法子数组的长度。如果找不到这样的子数组说明无法把 x 减到 0返回 -1。这个转化是整道题的关键。正面看是“两端取数”侧面看是“中间留数”。一旦转化成“寻找和为 target 的最长子数组”滑动窗口就顺理成章了。4.2 代码与边界处理代码不长但边界条件值得仔细想def minOperations(nums: List[int], x: int) - int: total sum(nums) target total - x if target 0: return -1 if target 0: return len(nums) left 0 cur 0 max_len -1 for right, val in enumerate(nums): cur val while cur target: cur - nums[left] left 1 if cur target: max_len max(max_len, right - left 1) return -1 if max_len -1 else len(nums) - max_len先说边界。target 0 意味着 x 比整个数组总和还大两边怎么取都凑不够直接返回 -1。target 0 意味着 x 等于 total也就是说要把整个数组全部移除操作次数就是数组长度直接返回 len(nums)。注意这里依赖题目条件nums[i] 全是正整数。因为 target 0 时能凑成和为 0 的子数组只能是空数组最长合法子数组长度是 0所以结果是 n - 0 n。while cur target这个收缩条件也是基于数组元素都是正数这一点。因为全是正数窗口和 cur 是单调不减的一旦 cur 超过 target只能通过收缩左边界来减小它。如果数组里有负数这个 while 就不安全了因为加入负数也可能让 cur 下降窗口就不是简单的“大了就缩”的关系。用个例子验证一下。nums [1,1,4,2,3]x 5。total 11target 6。我们需要找和为 6 的最长连续子数组。滑动窗口扫一遍能找到一个子数组 [1,1,4] 和为 6长度 3还有一个 [4,2] 长度 2。最长是 3所以返回 5 - 3 2。实际操作就是移除左边两个 1 和右边一个 3共 2 次操作跟答案一致。4.3 为什么这道题看起来不像窗口却还是要用窗口很多人刷到这道题时觉得它跟滑动窗口没什么关系因为题目表面上是“从两端拿东西”没提“连续子串”这几个字。但一旦你做了“中间留数”的转化它就变成了非常典型的“最长合法连续子数组”问题。从窗口角度看这个问题的合法条件是“窗口内数字和等于 target”。右指针不断向右扩展窗口总和超过 target 时收缩左边界收缩完如果总和恰好等于 target就更新 max_len。这完美契合前面说的“变长窗口求最长合法子串”模型。对比第二题你会发现第二题是“合法后收缩找最短”更新在收缩前第三题是“收缩后检查合法性找最长”更新在收缩后。两者都是滑动窗口但答案更新的位置完全不同。这个差异就是滑动窗口题最值得花时间理清楚的地方。5. 三题对照模板、复杂度与适用场景5.1 快速对照表我把三题放在一起对比一下这样面试前扫一眼就能想起来题目窗口类型合法条件更新答案时机时间复杂度空间复杂度字母异位词定长窗口窗口长度等于 len(p) 且频次一致窗口长度固定时比较相等就记录O(n)O(26)最小覆盖子串变长最短match need_cnt窗口合法时先记录再收缩O(n)O(k)k 是字符种类数将 x 减到 0变长最长窗口和 target先收缩收缩完再判断并更新O(n)O(1)三题的共同点是都维护了一个满足某种条件的连续窗口都通过左右指针的移动保证每个元素至多被访问两次所以时间复杂度都是 O(n)。差别主要在窗口长度是固定还是可变、答案是求最大还是最小、以及更新答案的位置。5.2 通用模板的最终形态如果一定要抽象出模板我会写成这样def sliding_window(nums): left 0 cur 0 res ... for right, x in enumerate(nums): cur x # 右边界加入窗口 while 窗口不满足条件: cur - nums[left] left 1 # 根据题目类型在合适的位置更新 res # 最短合法窗口收缩前更新 # 最长合法窗口收缩后更新 return res这个模板能覆盖大部分滑动窗口题但你要额外记住不是所有题都适合这个模板。比如第一题是定长窗口不需要 while 收缩用 if 控制长度即可。又比如“滑动窗口的最大值”这类题目其实需要的是单调队列而不是普通滑动窗口。所以模板是起点不是终点。5.3 什么时候不能用滑动窗口滑动窗口的好用是有前提的窗口的扩张和收缩必须能单调地改变窗口状态。最典型的反面例子是数组中存在负数时窗口和可能因为加入一个负数而下降导致“窗口和大于 target”这个条件无法通过简单收缩左边界来恢复。比如要找“和为 target 的最长子数组”如果数组里有负数当 cur target 时你不能确定收缩左边界一定能让 cur 降到 target因为后面可能遇到负数又降下去。这种情况需要换成前缀和 哈希表来解或者用其他方法。刷题的时候一定要看题目里有没有“正数”这个约束这直接决定了能不能用标准滑动窗口。另外如果题目要求窗口内元素满足的条件不是“可累积、可撤销”的滑动窗口也不适用。比如让你维护窗口内所有元素的中位数窗口滑动时虽然也能增量更新但复杂度会上去通常会用有序数据结构或树状数组而不是简单窗口。6. 常见问题与避坑经验6.1 边界条件的四个高频坑边界问题真的能毁掉一次面试。我整理了几个高频坑第一个s 或 nums 为空。第一题和第二题都要先判断空字符串第三题如果 nums 为空total 0target 可能是负数也可能等于 0要小心。空数组时根本不存在合法的滑动窗口。第二个p 比 s 长。第一题里如果 n k直接返回空列表不需要进入主逻辑。第三个第三题的 target 0。x 大于 total 时直接返回 -1这个很多人会漏掉。还有一种情况是 target 很大但数组里找不到合法子数组最后返回 -1 而不是 0。第四个第二题找不到覆盖子串时返回空字符串。判断条件就是 min_len 是否仍然是 float(inf)。我最开始写过不加这个判断的版本结果返回了 s[start:startinf] 这种诡异结果调试了半天。6.2 性能陷阱别在循环里做重操作滑动窗口本来是为了省时间但如果你在循环里做了不该做的事复杂度又会被拉回去。最常见的错误是在循环里重新排序窗口内容或者重新构造整个窗口的字符计数。比如第一题如果每次 right 移动后都用sorted(s[left:right1])去比较那滑动窗口就名存实亡了。正确的做法是只更新新进入和移出的那一个字符。另一个常见问题是频繁创建对象。在第二题里如果每次循环都重新window {}那之前维护的计数全部作废窗口就变成了每轮重新统计。正确的姿势是在循环外面初始化只在循环内做增量修改。还有一个性能相关的细节第三题的while cur target收缩过程总次数不会超过 n因为 left 最多向右移动 n 次。所以虽然是内层循环但均摊复杂度依然是 O(n)。面试时如果有人问“这个 while 会不会导致 O(n²)”你可以用这个均摊思路解释。6.3 刷这几道题时我最想告诉你的经验这三道题是我觉得滑动窗口里最值得反复刷的入门组合。我的建议是别死记模板而是每一题都自己动手画一画窗口的滑动过程把 left 和 right 的移动轨迹、match 或 cur 的变化写下来。比如第二题你可以拿一个短字符串手写几步看看 match 什么时候增加、什么时候减少这样比背十遍代码都管用。再分享一个小技巧做滑动窗口题之前先问自己三个问题。第一窗口是定长还是变长第二窗口合法的条件是什么第三题目要求的是最大还是最小结果这三个问题想清楚代码基本就出来一大半了。特别是“最大还是最小”决定了更新答案的位置这是最容易踩坑的地方。这三题后面还可以继续扩展比如把异位词改成“找到字符串中所有字母异位词”的进阶版把减零问题改成“允许负数”的版本处理思路又会不一样。但作为滑动窗口的地基把我上面说的这些点吃透后面遇到更复杂的窗口题心里就不会慌了。