算法 · 算法

关于滑动窗口的一切

从滑动窗口是什么、什么时候能用,到两种正确性证明,讲清它为什么能放心剪掉暴力枚举里的大量子区间。

本文目录

从一个具体问题说起

给定一个元素都是正整数的数组和一个目标值 target,找出「元素之和大于等于 target 的最短连续子数组」,返回它的长度。例如数组 [2, 3, 1, 2, 4, 3]、target 为 7,答案是 2,因为 [4, 3] 的和恰好等于 7。

最直接的解法是暴力枚举:把所有起点和终点的组合都试一遍,一共有约 n² 个子数组,逐个求和判断。数组一大,这个做法就慢得不可接受。

能不能跳过其中大部分子数组,只检查少数几个?可以,这就是本文要讲的「滑动窗口」。

滑动窗口是什么?

滑动窗口(sliding window)是一种在数组或字符串上维护一个连续子区间的技巧。它用两个指针 left 和 right 夹出一个窗口 [left, right)(左闭右开,覆盖 left 到 right - 1 这些下标)。right 向右移动,把新元素「纳入」窗口;left 向右移动,把元素「移出」窗口。

关键在于两个指针都只朝一个方向移动、从不回退。left 最多走 n 步,right 也最多走 n 步,所以整个过程的总移动量是 O(n)。这使它能把很多原本需要 O(n²) 枚举子区间的问题降到 O(n)。

按窗口大小是否固定,滑动窗口分成两类:

  • 固定窗口:窗口长度固定为 k,整体向右平移,比如求「长度为 k 的子数组的最大和」。
  • 可变窗口:窗口大小由某个条件驱动,right 负责扩张、left 负责收缩。本文的「最短连续子数组」就属于这一类,另外「不含重复字符的最长子串」也常用它。

什么时候能用滑动窗口?

不是所有子数组问题都能用滑动窗口。判断能不能用,看两点。

第一,问题问的必须是连续的子数组或子串,而不是可以跳着取元素的子序列。

第二,也是最关键的一点:问题要有单调性。意思是,当窗口变大时,某个「代价」只增不减;窗口变小时,这个代价只减不增。只有满足单调性,左指针「不回退」才是安全的。

本文例子里的「窗口元素之和」就是单调的:元素都是正整数,窗口越长和越大、越短和越小。如果元素允许出现负数,单调性就没了——去掉一个负数,窗口的和反而会变大。那时滑动窗口不再适用,比如「求和不超过 target 的最长子数组」在含负数的数组上就不能用滑动窗口解,得改用前缀和(prefix sum)之类的办法。

为什么说滑动窗口是暴力解的剪枝?

回到最开始的例子。设当前窗口是 [left, right),暴力枚举接下来会挨个尝试这些子数组:

  • A 类:起点仍是 left,终点继续往右扩,即 [left, right + 1)、[left, right + 2)……
  • B 类:起点换成 left + 1,终点从 left + 2 重新开始,一直到 right - 1,即 [left + 1, left + 2)、[left + 1, left + 3)……[left + 1, right - 1)。
  • C 类:起点换成 left + 1,终点保持 right 不变,即 [left + 1, right)。

滑动窗口做的事,是直接从当前窗口跳到 C 类,把 A 类和 B 类整段跳过。为什么敢跳过?假设当前 [left, right) 的和已经满足「大于等于 target」,并且 [left, right - 1) 不满足——也就是说 right 是当前 left 能取到的、最靠左的「够格」终点。

对 A 类:它们包含 [left, right) 的全部元素还要更多,和只会更大,一定满足条件,但长度更长。对「求最短」这个目标来说,它们被当前窗口支配,直接跳过。

对 B 类:它们都包含在 [left, right - 1) 里,而后者和不够 target,元素又都是正数,所以这些更短的子数组和只会更小,一定不满足,同样跳过。

于是只剩下 C 类这一个候选值得继续看。这就解释了滑动窗口的核心:它剪掉的不是「大概不行」的分支,而是已经证明「一定更差」或「一定不行」的分支。这种剪枝叫支配性剪枝(dominance pruning),是安全的——不会漏掉任何可能成为答案的窗口。

怎么证明滑动窗口不会漏掉最优解?

上面是直觉层面的解释。要严格说明「跳过是安全的」,可以给一个形式化证明。设最优解是 [L*, R*),即最短的满足条件的连续子数组。要证的是:算法一定会检查到这个窗口。

先看一个简单事实:因为 [L*, R*) 是最短解,它少一个元素就不成立了——[L*, R*-1) 的和一定小于 target,否则它自己就是更短的解。这意味着 R* 恰好是「起点为 L* 时,能凑够 target 的最靠左终点」。

而算法在 left = L* 时做的事情,正是让 right 一直往右扩、直到和第一次达到 target 才停下。由上面的结论,这个「第一次达到」的终点只能是 R*。所以算法必然访问 [L*, R*) 并记下它的长度。这是正向证明。

再用反证法看一遍,能更直接地看到矛盾所在。假设算法跳过了最优解 [L*, R*)。「跳过」意味着在右指针还没到 R* 时,左指针就越过了 L*。设左指针离开 L* 的那一刻右指针在 R,那么一定有 R < R*——否则右指针到 R* 时左指针还是 L*,就已经访问到最优解了。

左指针向右移动有一个必要条件:当前窗口 [L*, R) 的和已经大于等于 target。既然如此,[L*, R) 本身就是一个满足条件的连续子数组,而它的长度 R - L* 严格小于 R* - L*。这就凭空多出一个更短的解,与「[L*, R*) 是最短解」矛盾。

矛盾说明假设不成立,算法不会跳过最优解。这两种证明说的是同一件事:左指针只会在「窗口已经够格」时才向右移动,所以每个左端点对应的右端点都恰好停在「第一次够格」的位置,任何一个可能成为答案的窗口都不会被错过。

可以带走的几点

滑动窗口的本质可以概括成一句话:双指针加单调性。两个指针只朝一个方向走,靠的是「代价随窗口单调变化」这个前提。

想用滑动窗口前,先确认两件事:问题是否只关心连续区间,以及单调性是否成立。一旦单调性不成立(比如数组里有负数),「子集一定更小」这类推理就失效了,就得换成前缀和、哈希表等其他工具。

最后,把滑动窗口理解成「暴力解的剪枝」是准确的,但要注意它剪的是可证明的支配性剪枝,而不是靠猜。正确性证明,本质就是在论证这个剪枝不会把最优解剪掉。