02.2.1.2 滑动窗口模板与边界
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.2 数组、字符串与哈希 / 02.2.1 数组与双指针滑窗
02.2.1.2-001 滑动窗口适用什么问题?
一句话结论
在连续子数组/子串上求满足某条件的最长、最短或固定大小窗口时用滑动窗口;窗口左右边界单调右移,配合窗口内状态在线维护,整体 O(n)。
概念解释
- 连续区间:窗口是一段连续元素。
- 条件:无重复、和不超 K、包含目标字符等。
- 单调性:left、right 只增不减。
原理流程
- 判断问题是否为连续区间最优。
- 确认窗口合法性可由窗口内状态判定。
- 套扩张-收缩模板。
代码 / 图示
适用:最长/最短连续子串、定长子串统计
不适用:子序列(可不连续)、含负数且和无界的窗口收缩
常见误区
- 误区:所有子数组问题都用窗口;正解:不连续的子序列问题不适用。
- 误区:窗口可以左右回退;正解:回退会破坏线性复杂度。
追问
- Q:窗口与双指针关系? A:窗口是同向双指针,left 与 right 都向右移动。
- Q:含负数的最长和子数组能用窗口吗? A:不能靠收缩保证最优,需前缀和 + 哈希。
02.2.1.2-002 可变窗口通用模板怎么写?
一句话结论
right 遍历加入元素并更新状态;不合法时 while 收缩 left 直到重新合法;每轮合法后更新答案;模板分求最长与求最短两种更新口径。
概念解释
- 扩张:right 右移,纳入新元素。
- 收缩:left 右移,移除旧元素。
- 答案:合法窗口的长度/指标。
原理流程
- 初始化 left=0 与窗口状态。
- right 遍历,加入元素。
- while 不合法则收缩。
- 合法后更新最优答案。
代码 / 示例
int left = 0, ans = 0;
for (int right = 0; right < n; right++) {
add(a[right]);
while (!valid()) remove(a[left++]);
ans = Math.max(ans, right - left + 1);
}
常见误区
- 误区:收缩用 if;正解:可能需连续移出多个元素,必须 while。
- 误区:先更新答案再收缩;正解:先保证合法,再记录窗口。
追问
- Q:求最短窗口模板差异? A:收缩到刚不合法前的最后一个合法态更新答案,命中后立即继续收缩。
- Q:窗口状态在哪更新? A:加入与移除成对修改计数/和。
02.2.1.2-003 定长窗口模板怎么写?
一句话结论
窗口大小 k 固定:先装入前 k 个元素,之后每轮 right 右移加入新元素、移除 left 旧元素,窗口大小恒为 k;O(n) 时间 O(1) 额外状态。
概念解释
- 大小固定:左右同步移动。
- 初始化:预填首窗。
- 滑动:一加一减。
原理流程
- 构建长度 k 的初始窗口并算状态。
- 记录首窗答案。
- 从 k 开始,加 right、减 left,更新答案。
代码 / 示例
long sum = 0;
for (int i = 0; i < k; i++) sum += a[i];
for (int i = k; i < n; i++) {
sum += a[i] - a[i - k];
// 窗口 [i-k+1, i],更新答案
}
常见误区
- 误区:定长窗口也用 while 收缩;正解:大小固定,直接一加一减。
- 误区:首窗答案漏记;正解:初始化后先记录一次。
追问
- Q:k > n 怎么办? A:按题目口径返回空或特殊值,避免下标越界。
- Q:定长窗口求什么常见? A:平均值、最大值(配单调队列)、异位词统计。
02.2.1.2-004 最长无重复字符子串(LC 3)怎么做?
一句话结论
哈希记录字符最近出现位置;right 纳入字符,若该字符在窗口内出现过,left 跳到上次位置 +1;每轮更新最大长度;O(n) 时间 O(字符集) 空间。
概念解释
- 窗口内字符无重复。
- 左边界只能跳转到已出现位置之后。
- 出现位置在窗口外不影响。
原理流程
- last 存字符下标。
- right 扫描,字符在窗口内则
left = max(left, last[c]+1)。 - 更新 last 与最大长度。
代码 / 示例
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> last = new HashMap<>();
int left = 0, ans = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (last.containsKey(c) && last.get(c) >= left)
left = last.get(c) + 1;
last.put(c, right);
ans = Math.max(ans, right - left + 1);
}
return ans;
}
常见误区
- 误区:left 直接赋值上次位置+1 不取 max;正解:旧位置可能在窗口左侧之外,需
max(left, …)防回退。 - 误区:重复字符从窗口逐个删;正解:直接跳到重复点之后,跳过中间字符。
追问
- Q:字符集有限可用什么? A:数组计数/记录下标,替代哈希。
- Q:要返回子串本身? A:记录最大长度对应的起点下标。
02.2.1.2-005 最小覆盖子串(LC 76)怎么做?
一句话结论
右指针扩张到窗口覆盖目标全部字符,再左指针收缩到刚不覆盖前记录最短窗口;用需求计数与窗口计数差值判断合法性;O(n) 时间 O(字符集) 空间。
概念解释
- need:目标字符需求量。
- 缺口数:还需满足的字符种类数。
- 收缩:在覆盖前提下尽量缩短。
原理流程
- 统计 need 与缺口。
- right 扩张,更新窗口计数与缺口。
- 缺口为 0 时 while 收缩,更新最短记录。
- 移出字符破坏覆盖后停止。
代码 / 示例
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>(), win = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
int left = 0, miss = need.size(), start = 0, len = Integer.MAX_VALUE;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
win.merge(c, 1, Integer::sum);
if (need.containsKey(c) && win.get(c).equals(need.get(c))) miss--;
while (miss == 0) {
if (right - left + 1 < len) { start = left; len = right - left + 1; }
char d = s.charAt(left++);
if (need.containsKey(d)) {
if (win.get(d).equals(need.get(d))) miss++;
win.merge(d, -1, Integer::sum);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
常见误区
- 误区:逐个字符比对窗口是否覆盖;正解:用缺口种类数 O(1) 判断。
- 误区:收缩时先移除再判合法;正解:先记录当前合法窗口,再移出。
追问
- Q:目标含重复字符怎么处理? A:need 按次数统计,窗口计数达到需求量才算满足。
- Q:找不到覆盖窗口? A:len 保持初始值,返回空串。
02.2.1.2-006 长度最小的子数组(LC 209)怎么做?
一句话结论
数组含正数,滑动窗口扩张累加;和 ≥ target 时收缩左边界并记录最短长度;正数保证收缩不会漏解;O(n) 时间 O(1) 空间。
概念解释
- 正数:移出元素只会让和减小。
- 合法:窗口和 ≥ target。
- 目标:最短长度。
原理流程
- right 累加窗口和。
- while 和 ≥ target:更新最短,移出 left。
- 结束返回最短长度。
代码 / 示例
public int minSubArrayLen(int target, int[] a) {
int left = 0, sum = 0, ans = Integer.MAX_VALUE;
for (int right = 0; right < a.length; right++) {
sum += a[right];
while (sum >= target) {
ans = Math.min(ans, right - left + 1);
sum -= a[left++];
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
常见误区
- 误区:含负数也用此窗口;正解:负数使和不随收缩单调,需前缀和 + 哈希。
- 误区:用 if 收缩;正解:要连续移出直到不合法,用 while。
追问
- Q:无满足子数组返回什么? A:按题目返回 0。
- Q:暴力前缀和做法? A:O(n²) 枚举两端,窗口法利用正数单调性优化。
02.2.1.2-007 字符串排列(LC 567)怎么做?
一句话结论
定长 k 窗口维护字符计数,窗口计数与目标计数完全相等即含排列;数组计数表逐个比较;O(n·字符集) 时间,字符集固定时常量。
概念解释
- 排列:字符多重集合相同。
- 窗口长度恒为目标长度。
- 计数表相等即匹配。
原理流程
- 统计目标计数与首窗计数。
- 每轮滑动:加右减左。
- 比较两计数表。
代码 / 示例
public boolean checkInclusion(String t, String s) {
int k = t.length();
if (k > s.length()) return false;
int[] need = new int[26], win = new int[26];
for (char c : t.toCharArray()) need[c - 'a']++;
for (int i = 0; i < k; i++) win[s.charAt(i) - 'a']++;
for (int i = k; i <= s.length(); i++) {
if (Arrays.equals(need, win)) return true;
if (i < s.length()) {
win[s.charAt(i) - 'a']++;
win[s.charAt(i - k) - 'a']--;
}
}
return false;
}
常见误区
- 误区:比较排序后的子串;正解:计数表在线维护,避免每次排序。
- 误区:窗口长度随收缩变化;正解:排列要求定长,不能可变收缩。
追问
- Q:如何 O(1) 判断计数表相等? A:维护匹配种类数,增减时同步更新。
- Q:目标含大写/其他字符? A:计数表按实际字符集开大。
02.2.1.2-008 找到所有字母异位词(LC 438)怎么做?
一句话结论
与排列同构:定长窗口滑动并维护计数,匹配时记录左端点下标;O(n) 时间 O(字符集) 空间。
概念解释
- 异位词:同长度同多重集合。
- 结果:所有匹配窗口的起始下标。
- 计数表在线滑动。
原理流程
- 目标计数与首窗计数。
- 滑动比较,匹配记录 left。
- 输出下标列表。
代码 / 示例
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int k = p.length();
if (k > s.length()) return res;
int[] need = new int[26], win = new int[26];
for (char c : p.toCharArray()) need[c - 'a']++;
for (int i = 0; i < k; i++) win[s.charAt(i) - 'a']++;
for (int i = k; i <= s.length(); i++) {
if (Arrays.equals(need, win)) res.add(i - k);
if (i < s.length()) {
win[s.charAt(i) - 'a']++;
win[s.charAt(i - k) - 'a']--;
}
}
return res;
}
常见误区
- 误区:记录右端点;正解:题目要求起始下标,记录 i-k。
- 误区:移出字符顺序写反;正解:先加新字符再减旧字符,或反之但计数一致。
追问
- Q:匹配种类数怎么维护? A:差值为 0 的种类计数,增删时更新。
- Q:重复匹配会重复记录吗? A:每个定长窗口只判断一次。
02.2.1.2-009 窗口和与定长平均值怎么求?
一句话结论
维护窗口累加和,滑动时 sum += a[right] - a[left-1];平均值为和 / k;O(n) 时间 O(1) 空间,避免每窗重新求和 O(nk)。
概念解释
- 重复计算:每窗从头求和是 O(nk)。
- 增量更新:一加一减保持窗口和。
- 平均值按 k 整除或浮点口径处理。
原理流程
- 首窗求和。
- 滑动更新和。
- 按题目口径记录结果。
代码 / 示例
double[] avg(int[] a, int k) {
double[] res = new double[a.length - k + 1];
long sum = 0;
for (int i = 0; i < k; i++) sum += a[i];
res[0] = (double) sum / k;
for (int i = k; i < a.length; i++) {
sum += a[i] - a[i - k];
res[i - k + 1] = (double) sum / k;
}
return res;
}
常见误区
- 误区:整数除法截断;正解:先转浮点再除。
- 误区:和用 int 累加溢出;正解:宽类型累加,注意上溢。
追问
- Q:k=1 时? A:窗口即单元素,结果为原数组。
- Q:窗口和为负数场景? A:和仍可增量维护,收缩单调性另说。
02.2.1.2-010 窗口状态有哪些常见维护方式?
一句话结论
窗口状态可以是计数表、哈希集合、窗口和、最值结构;加入与移除操作成对实现,保证状态始终等于当前窗口内容;状态查询 O(1) 或按结构量级。
概念解释
- 计数:字符/数字出现次数。
- 集合:存在性判断。
- 聚合:和、最值。
原理流程
- 确定合法性依赖的统计量。
- 实现 add/remove 两个更新函数。
- 合法性判断读状态。
代码 / 图示
加入:win[c]++
移除:win[c]--
判断:count / sum / 最值结构
常见误区
- 误区:只写加入更新,漏移除;正解:收缩时必须同步移除状态。
- 误区:状态在窗口外累积;正解:移除后计数归零要及时清理。
追问
- Q:最值状态用什么结构? A:堆或单调队列,见 02.3.2 相关章节。
- Q:计数表用数组还是哈希? A:字符集小且连续用数组,范围散用哈希。
02.2.1.2-011 收缩条件为什么用 while 而不是 if?
一句话结论
一次移出可能不足以让窗口合法,需要连续移出直到重新满足条件;if 只移一次,残留非法状态会导致答案错误。
概念解释
- 非法可能由多个元素造成。
- while 保证退出时窗口合法。
- 每移出一个都要更新状态。
原理流程
- 进入收缩时窗口非法。
- while 判断仍非法则继续移出。
- 合法后退出。
代码 / 示例
while (!valid()) {
remove(a[left]);
left++;
}
常见误区
- 误区:套用 if 收缩;正解:最短窗口类问题必须 while 到边界。
- 误区:while 内忘记更新状态;正解:移出元素必须同步减计数/减和。
追问
- Q:定长窗口需要 while 吗? A:不需要,大小固定,一加一减即可。
- Q:while 会不会死循环? A:left 单调右移,最多到 right,不会回退。
02.2.1.2-012 窗口左边界为什么不能回退?
一句话结论
窗口单调性保证每个元素最多进、出窗口一次,从而 O(n);left 回退会重复扫描已处理区间,退化为多重循环。
概念解释
- 单调性:left 只增不减。
- 不变量:[left, right] 是当前合法候选。
- 回退破坏线性。
原理流程
- 收缩只向右移动 left。
- 已移出的元素不再纳入。
- 整体移动次数 O(n)。
代码 / 图示
窗口:[L, R],L 只右移
回退:L 向左 → 重复扫描,复杂度上升
常见误区
- 误区:为了找更长窗口把 left 拉回;正解:更长窗口只能等 right 继续扩张。
- 误区:重复字符直接把 left 拉到开头;正解:跳到重复点之后即可。
追问
- Q:什么情况下窗口可以重开? A:问题要求互不重叠的多段窗口时,按段重置左右指针。
- Q:线性复杂度怎么保证? A:left、right 各最多移动 n 次。
02.2.1.2-013 负数为什么会破坏窗口收缩的单调性?
一句话结论
滑动窗口收缩依赖"移出元素只会让指标单调变化";含负数时移出元素可能让和增大,无法判断收缩方向,普通窗口失效,需前缀和 + 哈希。
概念解释
- 正数:移出后和减小。
- 负数:移出后和可能增大。
- 单调性缺失:收缩无法保证最优。
原理流程
- 检查元素是否可为负。
- 和类问题含负则放弃窗口收缩。
- 改用前缀和统计满足条件的子数组。
代码 / 图示
非负:和随收缩单调下降 → 窗口成立
含负数:和波动 → 前缀和 + 哈希计数
常见误区
- 误区:窗口和问题默认元素非负;正解:先确认数值范围,含负需换框架。
- 误区:前缀和也要求非负;正解:前缀和本身不要求,单调性二分才要求。
追问
- Q:含负数求最长和子数组? A:前缀和 + 哈希记录最早前缀和位置。
- Q:计数类窗口受负数影响吗? A:计数与正负无关,仍可用窗口。
02.2.1.2-014 窗口内最大值为什么要交给单调队列?
一句话结论
普通窗口每次重扫最大值 O(nk);单调队列在线维护候选下标,队首即当前最值,每个元素进出队一次,整体 O(n);详见 02.3.2 单调队列章节。
概念解释
- 堆也可维护最值 O(n log k)。
- 单调队列利用窗口位置单调性 O(n)。
- 队尾剔除劣值,队首淘汰越界。
原理流程
- 新元素从队尾剔除劣值。
- 队首越界出队。
- 队首为窗口最值。
代码 / 图示
窗口最值:
堆:O(n log k)
单调队列:O(n),存下标保窗口淘汰
常见误区
- 误区:窗口题每次遍历取最值;正解:窗口滑动后最值可在线维护。
- 误区:单调队列存值即可;正解:必须存下标才能判断越界。
追问
- Q:LC 239 滑动窗口最大值? A:单调递减双端队列,队首最大。
- Q:最小值怎么改? A:队列改单调递增,队首最小。
02.2.1.2-015 求最长与求最短窗口在更新答案上有什么区别?
一句话结论
求最长:每次合法后用窗口长度更新最大值,尽量晚收缩;求最短:收缩到刚要不合法前记录最短,尽量早收缩;更新时机不同。
概念解释
- 最长:合法即记录,收缩只为消除非法。
- 最短:合法后持续收缩,记录每个收缩态长度。
- 方向相反。
原理流程
- 明确目标最长还是最短。
- 最长:合法后更新 max。
- 最短:while 收缩过程中持续更新 min。
代码 / 图示
最长:ans = max(ans, R-L+1)
最短:while 合法 { ans = min(...); 移出; }
常见误区
- 误区:两类题套用同一更新时机;正解:最短必须在收缩循环内更新。
- 误区:最短窗口收缩过头才记录;正解:记录的是收缩前最后一个合法长度。
追问
- Q:最长合法窗口收缩条件? A:非法才收缩,合法状态尽量保留宽度。
- Q:最短窗口扩张到合法后? A:立即进入收缩尝试更短。
02.2.1.2-016 什么时候更新窗口答案最合适?
一句话结论
先让窗口达到合法状态再更新答案;扩张后非法则收缩到合法,合法那一刻的窗口才是候选;避免把非法窗口计入最优值。
概念解释
- 非法窗口指标不满足题目要求。
- 先状态后答案:顺序不能反。
- 每轮至多更新一次最优。
原理流程
- 加入 right。
- 收缩至合法。
- 更新最优答案。
代码 / 示例
add(right);
while (!valid()) remove(left++);
ans = Math.max(ans, right - left + 1);
常见误区
- 误区:扩张后立刻更新答案;正解:可能仍非法。
- 误区:收缩过程中更新非法长度;正解:只在合法态记录。
追问
- Q:定长窗口何时更新? A:窗口大小到位后每轮记录。
- Q:答案需要记录窗口内容? A:同时记录起止下标,最后切片。
02.2.1.2-017 计数表用数组还是哈希表?
一句话结论
字符集小且连续(小写字母、数字)用定长数组,访问 O(1) 且缓存友好;字符范围散或为对象键时用哈希表;两者都要处理计数归零。
概念解释
- 数组:下标直接映射,长度固定。
- 哈希:键任意,平均 O(1)。
- 归零:移除后计数为 0,判断合法性时注意。
原理流程
- 统计字符取值范围。
- 范围确定用数组,否则哈希。
- 增减计数后更新合法性状态。
代码 / 示例
int[] win = new int[26];
win[c - 'a']++;
// 散字符:Map<Character,Integer>
常见误区
- 误区:所有场景都用哈希;正解:小字符集数组更快更省。
- 误区:计数为 0 仍留在哈希里影响判断;正解:比较时按缺省 0 处理。
追问
- Q:Unicode 大范围字符? A:用哈希表,数组不可开。
- Q:计数相等怎么快速判断? A:维护匹配种类数,避免整表比较。
02.2.1.2-018 滑动窗口有哪些边界要单独处理?
一句话结论
空串/空数组、目标长度大于输入、窗口永远不合法、单元素、全部字符相同、目标含重复字符;初始化与返回值口径要先确认。
概念解释
- 规模边界:k > n 直接返回。
- 合法性边界:始终不合法返回默认值。
- 计数边界:重复字符需求量。
原理流程
- 入口判空与长度比较。
- 初始化首窗。
- 收尾处理未命中情况。
代码 / 图示
s 为空 / t 为空
k > n
窗口从不满足条件
目标字符不在输入中
常见误区
- 误区:首窗未判断 k ≤ n;正解:先比较长度防越界。
- 误区:找不到答案返回空串还是 0;正解:按题目口径区分。
追问
- Q:目标字符重复多次? A:need 按次数,窗口计数达到才算满足。
- Q:输入长度正好等于 k? A:只判断首窗,不进入滑动。
02.2.1.2-019 滑动窗口与同向双指针是一回事吗?
一句话结论
窗口是同向双指针的一种:两指针同方向、中间区间为维护对象;快慢指针也是同向,但前者维护区间状态,后者维护写位置,语义不同。
概念解释
- 窗口:[L, R] 整体作为状态对象。
- 快慢:slow 写位、fast 扫描位。
- 共同前提:指针单向移动。
原理流程
- 区分问题是维护区间还是原地划分。
- 区间聚合用窗口。
- 原地保留用快慢。
代码 / 图示
窗口:L、R 之间有窗口状态
快慢:slow 写,fast 读
常见误区
- 误区:同向指针都叫窗口;正解:原地划分场景是快慢指针。
- 误区:窗口必须有收缩;正解:定长窗口只同步滑动。
追问
- Q:相向双指针与窗口区别? A:相向从两端靠拢,窗口从左向右推进。
- Q:窗口能解决原地去重吗? A:去重用快慢覆盖写更直接。
02.2.1.2-020 滑动窗口的复杂度怎么推?
一句话结论
right 遍历 n 次,left 单调右移最多 n 次,窗口状态每次 O(1) 更新,整体时间 O(n);空间为计数表/哈希大小,字符集固定时 O(1)。
概念解释
- 双指针各移动不超过 n。
- 每轮状态更新常数次。
- 复杂度与窗口大小无关。
原理流程
- 统计 right 步数:n。
- 统计 left 步数:≤ n。
- 状态更新 O(1),合计 O(n)。
代码 / 图示
right: 0 → n-1,n 步
left: 0 → n,≤ n 步
总操作 O(n),辅助 O(字符集)
常见误区
- 误区:窗口每滑一次重扫窗口内容所以 O(nk);正解:状态增量维护,不重扫。
- 误区:计数表比较整表是 O(字符集);正解:维护匹配种类数可做到 O(1) 判断。
追问
- Q:什么操作会让窗口题退化? A:窗口内排序、集合去重重扫等非常数状态更新。
- Q:空间 O(1) 的条件? A:字符集/值域固定可数,计数表大小与 n 无关。