滑动窗口
滑动窗口是用左右两个边界维护数组或字符串中的一段连续区间,边界移动时只处理刚进入和刚离开的元素。区间和、字符频次这些统计结果因此可以接着上一轮算,不用每次把整段重新扫一遍,暴力的 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 记录还差多少个字符才能覆盖,初值是目标长度,重复的字符也逐个计入。
窗口移动时,计数按下面三步更新:
- 加入字符
c之前,如果have[c]<need[c],说明c正好补上一个缺口,missing减一;然后have[c]加一。 missing变成 0,说明当前窗口已经覆盖目标。先记录答案,再尝试移走左端字符。- 移走
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 保存当前窗口,有什么问题?
substring 每次都会创建新字符串并复制字符。如果创建的子串长度从 1 增长到 n,累计复制量就是 O(n²),把线性算法拖成了平方级。只记录最优区间的左右边界,循环结束后再调用一次 substring,就能避免这些分配。
11.4 数组里有负数,还能用滑动窗口吗?
要看窗口条件。负数会让「按区间和收缩」的依据失效:加入负数让和下降,移除负数让和上升。但按频次判断的窗口和固定长度窗口不受影响。含负数时,统计和等于目标的子数组个数可以用前缀和加哈希表;求和至少达到目标的最短区间,可以用前缀和加单调队列。
12. 面试题卡片
13. 参考资料
- Java SE 21:String
- Java SE 21:Character
- Java SE 21:HashMap
- Antti Laaksonen:Competitive Programmer’s Handbook
- OpenJDK 21:StringUTF16 源码
- LeetCode:Find All Anagrams in a String
- LeetCode:Minimum Size Subarray Sum
来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明