企业官网建设流程全解析

如果你最近在刷算法题，滑动窗口这四个字应该没少听。我第一次被它真正搞明白，就是被“找到字符串中所有字母异位词”这题逼的。当时暴力解法写起来很简单，但一跑大用例就超时，怎么优化都觉得别扭。后来刷到“把 x 减到 0 的最小操作数”时又愣了一下：这题看起来跟窗口八竿子打不着，结果绕来绕去，核心还是滑动窗口。所以我打算把这三道经典题放在一起聊，从异位词一路聊到减零问题，把窗口为什么能省时间、代码怎么写才不容易错、遇到变形怎么一眼认出来，一次讲透。今天这篇适合正在准备面试的人，也适合已经刷过一些题、但总觉得滑动窗口换个壳就不会写的人。

1. 滑动窗口这套模板，到底在解决什么问题

1.1 从暴力解到窗口思想：为什么窗口能省时间

先聊个底层问题：滑动窗口到底在优化什么？

拿异位词来说，暴力解法是枚举 s 中所有长度为 len(p) 的子串，然后挨个判断这个子串是不是 p 的异位词。假设 s 的长度是 n，p 的长度是 m，那枚举的子串数量是 n-m+1，每个子串如果要排序再比较，复杂度就是 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 = "cbaebabacd"，p = "abc"，k = 3。

窗口先走到 "cba"，长度正好 3，window 里 a、b、c 各一个，need 也是 abc 各一个，相等，记录起点 0。之后窗口滑动到 "bae"，a、b、e 各一个，不等于 need，不记录。继续滑，到 "bac" 时，窗口内是 b、a、c，又相等了，记录起点 6。最终结果就是 [0, 6]。

这里有个小细节：为什么窗口超长时用 if 而不是 while？因为窗口长度是固定 k，right 每次只加一个字符，left 也最多只需要移出一个字符就能恢复长度 k，所以 if 就够了。如果你写成 while，也不会出错，但语义上没必要。

2.3 为什么用计数数组而不是哈希表

很多解法里会用字典来统计字符频次，但在这道题里，计数数组更合适。因为题目明确说了 s 和 p 只包含小写字母，总共就 26 个字符。用长度为 26 的数组，比较两个数组是否相等可以直接window == need，Python 对列表的相等判断是按元素逐个比较，速度快，代码也简洁。

如果用字典，需要处理“键不存在”的情况，还得写循环逐项比较，代码会啰嗦不少。当然，如果题目改成包含任意 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:start+min_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 = 11，target = 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 快速对照表

我把三题放在一起对比一下，这样面试前扫一眼就能想起来：

三题的共同点是都维护了一个满足某种条件的连续窗口，都通过左右指针的移动保证每个元素至多被访问两次，所以时间复杂度都是 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 = 0，target 可能是负数，也可能等于 0，要小心。空数组时根本不存在合法的滑动窗口。

第二个，p 比 s 长。第一题里如果 n < k，直接返回空列表，不需要进入主逻辑。

第三个，第三题的 target < 0。x 大于 total 时直接返回 -1，这个很多人会漏掉。还有一种情况是 target 很大但数组里找不到合法子数组，最后返回 -1 而不是 0。

第四个，第二题找不到覆盖子串时返回空字符串。判断条件就是 min_len 是否仍然是 float('inf')。我最开始写过不加这个判断的版本，结果返回了 s[start:start+inf] 这种诡异结果，调试了半天。

6.2 性能陷阱：别在循环里做重操作

滑动窗口本来是为了省时间，但如果你在循环里做了不该做的事，复杂度又会被拉回去。

最常见的错误是在循环里重新排序窗口内容，或者重新构造整个窗口的字符计数。比如第一题，如果每次 right 移动后都用sorted(s[left:right+1])去比较，那滑动窗口就名存实亡了。正确的做法是只更新新进入和移出的那一个字符。

另一个常见问题是频繁创建对象。在第二题里，如果每次循环都重新window = {}，那之前维护的计数全部作废，窗口就变成了每轮重新统计。正确的姿势是在循环外面初始化，只在循环内做增量修改。

还有一个性能相关的细节：第三题的while cur > target收缩过程，总次数不会超过 n，因为 left 最多向右移动 n 次。所以虽然是内层循环，但均摊复杂度依然是 O(n)。面试时如果有人问“这个 while 会不会导致 O(n²)”，你可以用这个均摊思路解释。

6.3 刷这几道题时，我最想告诉你的经验

这三道题是我觉得滑动窗口里最值得反复刷的入门组合。我的建议是别死记模板，而是每一题都自己动手画一画窗口的滑动过程，把 left 和 right 的移动轨迹、match 或 cur 的变化写下来。比如第二题，你可以拿一个短字符串，手写几步，看看 match 什么时候增加、什么时候减少，这样比背十遍代码都管用。

再分享一个小技巧：做滑动窗口题之前，先问自己三个问题。第一，窗口是定长还是变长？第二，窗口合法的条件是什么？第三，题目要求的是最大还是最小结果？这三个问题想清楚，代码基本就出来一大半了。特别是“最大还是最小”决定了更新答案的位置，这是最容易踩坑的地方。

这三题后面还可以继续扩展，比如把异位词改成“找到字符串中所有字母异位词”的进阶版，把减零问题改成“允许负数”的版本，处理思路又会不一样。但作为滑动窗口的地基，把我上面说的这些点吃透，后面遇到更复杂的窗口题心里就不会慌了。