跳到主要内容
约 17 分钟7 张卡

滑动窗口

滑动窗口是用左右两个边界维护数组或字符串中的一段连续区间,边界移动时只处理刚进入和刚离开的元素。区间和、字符频次这些统计结果因此可以接着上一轮算,不用每次把整段重新扫一遍,暴力的 O(n²) 就降到了 O(n)。

写窗口题时,要先想清楚左边界凭什么可以往前移、答案在什么时候更新,以及重复字符和已经离开窗口的元素怎么处理,再把这些判断落实到循环里。用 Java 写字符串题时,还要先说清楚「一个字符」按什么单位计数。

1. 面试核心​

先记住这几条,再读正文
  • 固定长度窗口每次加入一项、移除一项,不依赖单调性,所以含负数的数组也能用。卡 · 连续区间
  • 查找全部字母异位词时,窗口长度固定为模式长度,比较完整频次并保留重叠的匹配起点。卡 · 全部字母异位词的起点
  • 求最长无重复子串时,用哈希表记录字符最近一次出现的位置,左端只向前跳,期望时间复杂度为 O(n)。卡 · 可变窗口
  • 要返回最长片段,应只保存最优边界,最后截取一次;按码点计数时,截取前先换成 UTF-16 偏移。卡 · 返回最长片段
  • 正数数组求和达标的最短区间,要在达标时反复记录并收缩,无解返回 0。卡 · 正数数组的最短达标区间
  • 求最小覆盖子串时,要按频次判断覆盖,窗口满足要求时先记录答案,再收缩左端。卡 · 最小覆盖与重复计数
  • 单调队列只保留还没过期、仍可能成为最大值的下标,所有窗口的最大值总共 O(n) 时间求出。卡 · 窗口最大值与单调队列
  • Java String 的下标按 UTF-16 编码单元(code unit)计数,一个码点(code point)可能占两个 char。

2. 连续区间​

滑动窗口只适用于连续片段。下面这些问题都在找满足某个条件的连续区间,是窗口的典型场景:

  • 求最长无重复子串。
  • 求非负数组中,和至少达到目标的最短子数组。
  • 求满足指定字符数量的最小覆盖区间。
  • 统计固定长度区间的和、平均值、频率或最大值。

如果题目允许跳过中间元素,那就是子序列或组合问题,窗口不再适用,要根据约束考虑动态规划、贪心或搜索。

窗口分两种。固定窗口的长度不变,每次加入一项、移除一项就行。可变窗口的长度随条件伸缩,这时要多回答一个问题:左端移走以后,原来的起点为什么可以不再考虑?

答案通常来自单调性。单调性指边界朝一个方向移动时,窗口的统计值也只朝一个方向变化。比如在非负数组里,加入元素只会让和变大或不变,移除元素只会让和变小或不变。求「和至少达到目标的最短子数组」时,窗口一旦达标,再往右扩只会更长,所以可以放心收缩左端。数组里有负数时,加入负数反而让和下降,这条推理就不成立了。不过固定长度的求和窗口不依赖单调性,含负数也照样能用。

3. 半开区间与不变量​

先把边界的含义定下来,窗口长度和答案的更新时机才不会算错。用半开区间 [left,right) 表示窗口时,约定如下:

  • left 指向窗口里的第一个元素。
  • right 指向下一个还没加入的元素,它本身不在窗口内。
  • 窗口长度是 right-left,空窗口时 left == right。

不变量是每一轮循环走到约定位置时都成立的条件,它是判断代码对不对的依据。下面的模板求最长有效窗口,它的不变量是:每次内层循环结束后,窗口都满足约束。

while right < n:
加入 a[right]
right += 1
while 当前窗口违反约束:
移除 a[left]
left += 1
用 right-left 更新最长长度

内层循环把导致违规的左端元素移出去,循环结束时窗口重新合法,这时用 right-left 更新答案才可靠。最短覆盖题正好相反:要在窗口还覆盖目标的时候记录答案,然后再尝试收缩。如果等到覆盖失效才记录,记下的就是一个不合法的区间。

4. 固定窗口​

固定窗口要比较所有长度为 k 的区间。窗口每右移一格,把新元素加进总和,再减掉刚离开的元素,就不用把整段重新求和:

static long maxWindowSum(int[] values, int k) {
if (k < 1 || k > values.length) throw new IllegalArgumentException();
long sum = 0;
long best = Long.MIN_VALUE;
for (int right = 0; right < values.length; right++) {
sum += values[right];
if (right >= k) sum -= values[right - k];
if (right >= k - 1) best = Math.max(best, sum);
}
return best;
}

输入 [-5,-2,-3]、k=2 时返回 −5:两个候选区间的和是 −7 和 −5。这里有两个细节。best 的初值用 Long.MIN_VALUE 而不是 0,否则全是负数时,0 会被误当成答案。sum 用 long,是因为多个 int 相加可能超出 int 范围。k 不在 1..values.length 范围内时,代码直接抛出 IllegalArgumentException。

每个元素最多进入、离开窗口各一次,时间是 O(n);只用了几个变量,额外空间是 O(1)。

4.1 全部字母异位词的起点​

字母异位词是字符种类与次数相同、排列顺序可以不同的字符串。查找模式 pattern 在 text 中的全部异位词时,只需比较长度等于 pattern.length() 的窗口。下面按原题 LC438 的小写英文字母条件使用 26 项数组,延续本文的 Java 参考实现;这不表示相关面试都指定了 Java。

static java.util.List<Integer> anagramStarts(String text, String pattern) {
if (pattern.isEmpty()) throw new IllegalArgumentException("empty pattern");
int[] need = new int[26], have = new int[26];
for (int i = 0; i < pattern.length(); i++) need[pattern.charAt(i) - 'a']++;
java.util.List<Integer> result = new java.util.ArrayList<>();
int k = pattern.length();
for (int right = 0; right < text.length(); right++) {
have[text.charAt(right) - 'a']++;
if (right >= k) have[text.charAt(right - k) - 'a']--;
if (right >= k - 1 && java.util.Arrays.equals(need, have)) {
result.add(right - k + 1);
}
}
return result;
}

每轮先加入 text[right],长度超过 k 时移除 text[right-k],再比较频次。只有窗口凑够 k 项才检查,need 与 have 的 26 项全相等时,起点是 right-k+1。相等次数不是集合判断,pattern="aab" 不能匹配 "abb"。

anagramStarts("cbaebabacd", "abc") 返回 [0,6];anagramStarts("abab", "ab") 返回 [0,1,2],说明相邻答案可以重叠。不能找到一次后直接跳过整个模式长度,否则会漏掉后两项。文本为空或比模式短时返回空列表;模式为空不在这里的接口约定内,直接抛异常。两个输入都必须非 null,且只含小写英文字母,函数不负责通用 Unicode 计数。

每次比较固定 26 项,时间为 O(text.length + pattern.length),不含输出列表的额外空间为 O(1)。输出本身最多与文本长度同阶;不应把存储所有答案的空间也称为常数。

5. 可变窗口​

最长无重复子串的窗口长度不固定:遇到重复字符,左端就要往前收。如果记下每个字符最近一次出现的位置,左端可以一步跳到旧位置之后,不用一格一格地挪。

下面的代码按 Unicode 码点计数。码点是 Unicode 给每个字符分配的编号,它和 Java char 的计数单位不一样,下一节会具体说明:

static int longestUniqueSubstring(String value) {
java.util.Map<Integer, Integer> lastSeen = new java.util.HashMap<>();
int left = 0, best = 0, position = 0;
for (int offset = 0; offset < value.length();) {
int codePoint = value.codePointAt(offset);
Integer previous = lastSeen.put(codePoint, position);
if (previous != null && previous >= left) left = previous + 1;
best = Math.max(best, position - left + 1);
offset += Character.charCount(codePoint);
position++;
}
return best;
}

abba 返回 2,A😀B😀 返回 3。代码里有两个下标:position 是码点下标,用来算窗口长度;offset 是在原字符串里读取时用的 UTF-16 偏移。每读一个码点,offset 就按它占用的 char 数往前推。

这段代码的不变量是:闭区间 [left,position] 里没有重复码点。遇到重复字符时,如果它的旧位置还在窗口内,left 就跳到旧位置之后;如果旧位置已经在窗口外,left 保持不动,否则会把已经排除的字符又放回窗口。代码用 previous >= left 做这个判断,写成 Math.max(left, previous + 1) 效果相同。以 abba 为例,处理最后一个 a 时 left 已经是 2,而 a 的旧位置是 0,left 不能退回 1。

两个边界都只向前走。哈希操作期望 O(1) 时,总时间是 O(n),这里的 n 是码点数。哈希表为每种出现过的字符存一个位置,空间取决于字符种类数。

5.1 返回最长片段​

求长度和返回子串只差一份最优边界,但不能把码点下标直接传给 substring。下面保留前面的无重复窗口,把最长时的 left 和码点长度记下来。并列时选择最早出现的片段,空串返回空串,输入要求非 null。

static String longestUniqueText(String value) {
java.util.Map<Integer, Integer> lastSeen = new java.util.HashMap<>();
int left = 0, position = 0, bestLeft = 0, bestLength = 0;
for (int offset = 0; offset < value.length();) {
int codePoint = value.codePointAt(offset);
Integer previous = lastSeen.put(codePoint, position);
if (previous != null && previous >= left) left = previous + 1;
int length = position - left + 1;
if (length > bestLength) {
bestLeft = left;
bestLength = length;
}
offset += Character.charCount(codePoint);
position++;
}
int start = value.offsetByCodePoints(0, bestLeft);
int end = value.offsetByCodePoints(start, bestLength);
return value.substring(start, end);
}

只在 length > bestLength 时更新,所以 "abba" 返回最早的 "ab",不会被同长的 "ba" 替换。循环结束后,offsetByCodePoints 把最优起点与长度转换成原字符串的 UTF-16 偏移,再调用一次 substring。"😀A😀B" 返回 "A😀B",起点不是把码点下标 1 直接当成 UTF-16 下标 1,否则会切进第一个 emoji 的代理对内部。

哈希访问期望 O(1) 时,遍历和最终边界换算总计 O(n),n 为码点数;没有在每轮创建窗口字符串。哈希表仍按不同码点保存最近位置,返回字符串另外占用与答案长度相应的空间。这里不把组合重音或多个码点组成的 emoji 序列当作一个字素簇,也不做 Unicode 归一化,计数规则不能与用户视觉字符混用。

5.2 正数数组的最短达标区间​

正数数组中,加入右端会增加区间和,移走左端会减少区间和。因此窗口一旦达到正数目标 target,就可以记录长度并继续收缩,直到和不再达标。下面按 LC209 的正数条件实现,无解返回 0,并允许空数组作为补充边界:

static int minLengthAtLeast(int target, int[] values) {
if (target <= 0) throw new IllegalArgumentException("target must be positive");
for (int value : values) {
if (value <= 0) throw new IllegalArgumentException("values must be positive");
}
long sum = 0;
int left = 0, best = 0;
for (int right = 0; right < values.length; right++) {
sum += values[right];
while (sum >= target) {
int length = right - left + 1;
if (best == 0 || length < best) best = length;
sum -= values[left++];
}
}
return best;
}

target=7、values=[2,3,1,2,4,3] 时返回 2,对应 [4,3];target=4、values=[1,4,4] 返回 1;数组总和仍不足目标或数组为空时返回 0。一次新元素加入后,可能有多个达标窗口,所以必须用 while 反复收缩,不能只移走一次左端。

sum 用 long,避免多个 int 相加溢出。例如 target = Integer.MAX_VALUE,values 包含两个 Integer.MAX_VALUE-1 时,单项不达标,两项之和已超出 int,正确答案是 2。数组长度和每项都是 Java int 范围时,正数总和可由 long 保存。校验与两个边界的累计移动都为 O(n),额外空间 O(1),函数不修改输入。

这里明确拒绝非正目标和含零或负数的输入,不将正数实现伪装成所有整数都适用的算法。比如 [1,-1,3]、目标 3,机械套用达标才收缩的过程,第一次达标记下长度 3,移走 1 后又变成 2,就可能漏掉独立的 [3]。含负数的另一个算法方向见负数与窗口条件。

6. Java String 的索引单位​

写字符串题之前,先要约定「一个字符」怎么算。Java 21 的 length() 和 charAt() 都按 UTF-16 编码单元计数,一个单元就是一个 char:

String value = "A😀B";
System.out.println(value.length()); // 4
System.out.println(value.codePointCount(0, value.length())); // 3

😀 占两个 char,所以这个字符串的 length() 是 4,码点数是 3。用户眼里的「一个字符」还可能更大:字素簇是屏幕上显示为一个字符的单位,它可以由多个码点组成,比如字母加组合重音,或者某些 emoji 序列。

所以题目要先说清楚按 ASCII、char、码点还是字素簇计数。只含小写字母、数字或 ASCII 时,可以用固定大小的 int 数组代替哈希表计数。处理国际化文本时,按约定的单位来计数;如果要返回原字符串的片段,还得把码点边界换算成 UTF-16 偏移,才能交给 substring。

7. 最小覆盖与重复计数​

最小覆盖子串要求窗口包含目标里的每个字符,而且次数要够。我们用三个量来记录:need 存目标中每个字符的频次,have 存窗口中每个字符的频次,没出现过的字符频次都算 0;missing 记录还差多少个字符才能覆盖,初值是目标长度,重复的字符也逐个计入。

窗口移动时,计数按下面三步更新:

  1. 加入字符 c 之前,如果 have[c]<need[c],说明 c 正好补上一个缺口,missing 减一;然后 have[c] 加一。
  2. missing 变成 0,说明当前窗口已经覆盖目标。先记录答案,再尝试移走左端字符。
  3. 移走 c 时,先把 have[c] 减一。如果这时 have[c]<need[c],覆盖被破坏,missing 加一,接着继续扩张右端。

为什么必须按频次,而不能只用集合判断字符有没有出现?目标 AAB 需要两个 A 和一个 B,窗口 AB 还缺一个 A;只看集合的话,A 和 B 都在,就会误判成已覆盖。目标为空串时,可以约定直接返回空串。计数时用的字符单位,和上一节一样以题目约定为准。

8. 窗口最大值与单调队列​

求每个窗口的最大值,麻烦在于当前最大值迟早会离开窗口,那时要马上知道下一个最大值是谁,所以得提前留好候选。单调队列就是用来存这些候选的:它是一个双端队列(两端都能加入和移除),里面存下标,并保证下标对应的值从队首到队尾严格递减。

维护它只需要两条规则:

  • 加入新下标前,从队尾弹出所有值不大于新值的下标。新元素至少和它们一样大,又比它们更晚离开窗口,只要新元素还在,这些旧元素就不可能成为最大值。
  • 每一轮从队首弹出已经过期的下标,也就是 index<=right-k 的项。窗口凑满 k 个元素后,队首就是当前最大值。

队列存下标而不是值,是因为只有下标能判断元素有没有离开窗口,也能区分值相同的两个元素。以 [1,3,3,2]、k=2 为例,三个窗口的最大值是 [3,3,3]。每个下标最多入队、出队各一次,总时间是 O(n);队列里最多有 k 个下标,空间是 O(k)。

9. 其他线性方法​

滑动窗口不是减少重复扫描的唯一办法,双指针和前缀和也常用来把 O(n²) 降到线性。这里只说明它们分别适合什么任务,推导放在各自的文章里。

9.1 相向双指针​

两个指针从两端往中间走。有序数组的两数之和,可以按当前和的大小排除一个端点;判断回文时,比较两端字符后一起向内收缩。指针移动的推导见双指针。

9.2 快慢指针​

原地去重和移除元素时,快指针负责读、慢指针负责写,具体做法见双指针。

链表判环让两个指针以不同速度前进,推导见链表。

9.3 前缀和​

前缀和花 O(n) 预处理,之后任意静态区间的和都能 O(1) 求出。数组含负数、要统计和等于目标的子数组个数时,可以把前缀和与哈希表结合起来,见前缀和。

10. 正确性证明​

证明一个滑动窗口算法正确,要回答两个问题:它有没有漏掉候选区间,以及被舍弃的起点为什么真的没用了。

第一个问题比较简单:右端逐个访问每个位置,所以每个位置都被当作区间终点考虑过。第二个问题要结合题目的约束来证明。

以无重复窗口为例,遇到重复字符 c 时,所有从旧 c 或更早位置开始、到当前位置结束的区间都包含两个 c,已经不合法;右端继续扩张,它们也只会更长,重复依然在。所以 left 可以直接移到旧 c 之后。最小覆盖的论证类似:窗口覆盖目标时已经记录了答案,从同一个起点出发、终点更靠右的区间只会更长,不可能更优,所以收缩左端不会漏掉答案。

11. 常见问题​

11.1 两层 while 嵌套,为什么还是线性时间?​

因为内层循环不会把左端重置回去,left 从上一轮停下的位置接着走。看总量:left 和 right 各自最多前进 n 次,加起来最多 2n 次移动。每次加入或移除元素是 O(1) 时,总成本就是 O(n)。

11.2 求最短区间和最长区间,答案分别在什么时候更新?​

11.3 每轮都用 substring 保存当前窗口,有什么问题?​

11.4 数组里有负数,还能用滑动窗口吗?​

12. 面试题卡片​

13. 参考资料​

来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明