滑动窗口
滑动窗口用左右边界维护连续区间，移动时只更新进入和离开的元素。这样就能复用区间和、字符频次等结果，减少重复扫描。本文从窗口的适用条件入手，依次讲解固定窗口、无重复子串、最小覆盖和窗口最大值。
重点是解释左边界的移动依据和答案的更新时机，并处理重复字符与过期元素。Java 示例还会说明字符串长度和下标的计数单位。
1. 面试核心
先记住这几条，再读正文- 固定窗口。 固定长度窗口每次加入一项、移除一项，因此也能计算含负数数组的区间和。卡 · 连续区间
- 无重复窗口。 求最长无重复子串时，窗口左端只向前移动，用哈希表记录字符最近位置的期望时间复杂度为 O(n)。卡 · 可变窗口
- 最小覆盖窗口。 求最小覆盖子串时，算法在窗口满足目标字符及其频次要求时记录答案，再收缩左端。卡 · 最小覆盖与重复计数
- 窗口极值。 单调队列保留未过期的最大值候选，因此可在 O(n) 总时间内求出所有窗口的最大值。卡 · 窗口最大值与单调队列
- Java 字符单位。 Java String 的下标按 UTF-16 编码单元（code unit）计数，一个码点（code point）可占两个 char。
2. 连续区间
滑动窗口处理的是数组或字符串中的连续片段。判断能否使用它时，先确认问题是否属于以下常见场景：
- 求最长无重复子串。
- 求非负数组中，和至少达到目标的最短子数组。
- 求满足指定字符数量的最小覆盖区间。
- 统计固定长度区间的和、平均值、频率或最大值。
如果允许跳过中间元素，就应按子序列或组合问题重新建模。这类问题可根据约束考虑动态规划、贪心或搜索。
固定窗口按长度移动，每次加入一项、移除一项即可。可变窗口还要说明：移走左端后，为什么可以舍弃原来的起点。
比如，在非负数组中，加入元素让和不减，移除元素让和不增。这种随边界移动保持同一变化方向的性质称为单调性。求最短达标和时，达到目标后就可以尝试收缩窗口。含负数时，加入负数会让和下降，移除负数会让和上升。所以，这套按和移动的证明失效，但固定长度的求和窗口仍然适用。
3. 半开区间与不变量
边界含义统一后，才能判断长度和更新时机。用半开区间 [left,right) 表示窗口时，需要明确以下三个约定：
- left 指向窗口第一个元素。
- right 指向下一个尚未加入的元素，因此右端点不在窗口内。
- 窗口长度为
right-left。
不变量是每轮在约定位置都成立的条件。下面求最长有效窗口，要求每次内层循环结束后，窗口都满足约束：
while right < n:
加入 a[right]
right += 1
while 当前窗口违反约束:
移除 a[left]
left += 1
用 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 值，避免全负数输入的答案被初值 0 覆盖。sum 也使用 long，以容纳超出 int 范围的累加结果。代码只接受 1 <= k <= values.length，范围之外会抛出参数异常。
每项至多进入和离开窗口一次，所以时间为 O(n)。算法只保留固定数量的变量，额外空间为 O(1)。
5. 可变窗口
最长无重复子串需要随字符重复情况调整左端。记录字符最近出现的位置后，就能直接跳过窗口内的旧字符。
下面按 Unicode 码点（code point）计数。码点是 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 偏移。代码先读取一个码点，再按它占用的 char 数推进 offset。
当前闭区间 [left,position] 内始终没有重复码点。遇到窗口内的重复字符时，left 跳到旧位置之后。如果旧位置已经在窗口外，就保持 left，避免把已排除的字符重新纳入窗口。代码用 previous >= left 判断，也可以用 Math.max(left, previous + 1) 保证左端只前进。比如处理 abba 的最后一个 a 时，left 已经是 2，应保持不变。
两个边界都只向前。哈希操作期望 O(1) 时，总时间为 O(n)，其中 n 表示码点数。哈希表为每种已见字符保存一个位置，空间取决于已见字符种类数。
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，所以示例的 char 长度为 4，码点数为 3。用户看到的一个完整字符称为字素簇，它还可以包含多个码点。比如，字母与组合重音、部分 emoji 序列，都需要把多个码点合起来显示。
因此，题目应明确按 ASCII、char、码点还是字素簇计数。只含小写字母、数字或 ASCII 时，可用固定大小的 int 数组替代哈希计数。处理国际化文本时，则要按约定选择索引单位。若返回原串片段，还需将码点边界转换为 UTF-16 偏移，供 substring 使用。
7. 最小覆盖与重复计数
最小覆盖子串要求窗口包含目标中的每个字符，并满足重复次数。设 need 保存目标频次，have 保存窗口频次，未出现字符的频次视为 0。missing 记录仍缺少的字符总数，初值是目标长度，重复项也计入。
移动窗口时，按以下三个步骤更新计数：
- 加入字符 c 前，若
have[c]<need[c]，说明它能补上一个缺口，missing 减一。随后增加have[c]。 - missing 为 0 时，当前窗口已覆盖目标。先记录答案，再尝试移走左端字符。
- 移走 c 时，先减少
have[c]。若这时have[c]<need[c]，就把 missing 加一，随后继续扩张右端。
比如，目标 AAB 需要两个 A 和一个 B。窗口 AB 仍缺一个 A，用集合只判断字符是否出现，就会误报覆盖。空目标可约定返回空串，频次处理则统一使用题目规定的字符单位。
8. 窗口最大值与单调队列
窗口右移后，原最大值会离开窗口，因此需要保留后续的最大值候选。双端队列支持从两端加入或移除元素。让队列保存下标，并保持对应值从队首到队尾严格递减，就得到这里的单调队列。
加入新下标前，弹出尾部所有不大于新值的项。新值更晚过期，且至少一样大，所以这些旧项可以淘汰。
每轮弹出队首所有 index<=right-k 的过期项。窗口达到 k 项后，队首就是最大值。保存下标能区分重复值并判断过期。
[1,3,3,2]、k=2 的窗口最大值为 [3,3,3]。每项至多入队、出队一次，总时间为 O(n)。队列最多保存 k 项，空间为 O(k)。
9. 其他线性方法
除了滑动窗口，还可以用其他方法减少重复扫描。下面按任务说明双指针与前缀和的用途，具体推导见对应文章。
9.1 相向双指针
有序两数和可按大小关系排除端点，回文判断则比较两端字符后向内收缩，指针移动的推导见双指针。
9.2 快慢指针
原地去重和元素移除用两个指针分别读取、写入，具体方法见双指针。
链表判环让两个指针以不同速度移动，推导见链表。
9.3 前缀和
前缀和用 O(n) 预处理支持 O(1) 的静态区间求和，含负数的目标和计数还可结合哈希表，见前缀和。
10. 正确性证明
证明滑动窗口正确，需要说明它为什么覆盖所有候选，又为什么可以排除旧起点。
右端逐项访问，所以每个位置都作为区间终点被考虑。左端移动时，则要结合约束证明被舍弃的起点已经无用。
比如，无重复窗口遇到重复字符 c 时，从旧 c 或它之前开始的当前区间都会包含两个 c。这些区间已失效，继续向右扩张也仍有重复，所以可将 left 移到旧 c 之后。最小覆盖则在当前已覆盖时先记录答案，再尝试收缩。原起点对应的更长区间不会比已经记录的区间更短。
11. 常见问题
下面集中说明复杂度、答案更新时机和 Java 子串分配中的常见疑问。
11.1 累计移动次数
嵌套的 while 仍可以是线性时间，因为左端保留上轮位置。两个边界各自至多前进 n 次，总次数至多 2n。所以，单次增删为 O(1) 时，总成本为 O(n)。
11.2 最短区间的更新时机
覆盖成立时先记录长度，再尝试收缩。覆盖失效后继续扩张右端。最长有效区间则在恢复有效后记录。
11.3 子串分配
每轮用 substring 保存窗口会产生额外字符串和复制。若创建的子串长度从 1 增长到 n，累计复制量就是 O(n²)。保存最佳边界，结束后再创建一次结果，就能避免这些重复分配。
11.4 负数与窗口条件
加入负数会让区间和下降，移除负数会让区间和上升，所以按和单调收缩的依据失效。频次条件与固定长度仍可用窗口。对于含负数的目标和计数，可考虑前缀和加哈希。对于和至少达标的最短区间，可考虑前缀和加单调队列。
12 · 面试题卡片
12.1 如何求最长无重复子串并证明线性时间？
出现公司：字节跳动、快手
考察重点：解释最近位置怎样让窗口恢复无重复，并说明左端为何只向前移动。区分 Java 的 char 与码点计数。
相关内容：可变窗口、Java String 的索引单位。
参考回答
用哈希表记录字符最近位置，并维护一个无重复窗口，就能求出最长长度。
遍历到 right 时，若字符的旧位置仍在窗口内，就将 left 移到旧位置后一位。这样移除了重复字符，再用 right-left+1 更新答案。若旧位置在窗口外，就保持 left，避免倒退。
right 与 left 都至多前进 n 次。哈希访问期望 O(1) 时，总时间为 O(n)，空间取决于字符种类数。只含 ASCII 时可改用数组，一般字符串则需按题目约定区分 char 与码点。
12.2 什么条件下可以使用滑动窗口？
出现公司：美团、字节跳动
考察重点：判断问题是否针对连续区间，并解释移动边界后怎样更新统计、排除候选。
参考回答
问题需要针对连续区间，并能随元素进入或离开更新统计结果。
固定窗口按长度移动即可，可变窗口还需证明左端单向移动不会漏掉更优答案。
比如，无重复窗口可跳过窗口内的旧字符，因为保留它的区间都已违规。非负数组也可利用区间和的单调性收缩。负数使按和收缩的证明失效，但固定长度窗口仍能处理负数。这时应按求和、计数或最短长度目标，选择前缀和、哈希表或单调队列。
12.3 最小覆盖子串如何处理目标中的重复字符？
出现公司：暂无已核验的公开来源（本站自测）
考察重点：说明重复项怎样计入缺口，并解释覆盖成立后为何先记录答案再收缩。
相关内容：最小覆盖与重复计数。
参考回答
用频次记录每个字符的需求，并将重复项计入 missing，才能判断是否完整覆盖。
目标 AAB 需要两个 A 和一个 B，所以窗口 AB 仍缺一个 A。新字符补上缺口时，missing 减一。missing 为 0 时先更新答案，再收缩左端。如果移除字符后频次低于需求，就将 missing 加一，继续扩张右端。
12.4 滑动窗口最大值为何用单调队列保存下标？
出现公司：暂无已核验的公开来源（本站自测）
考察重点：解释新元素为何能淘汰部分旧候选，以及下标怎样用于过期判断和累计操作次数分析。
相关内容：窗口最大值与单调队列。
参考回答
保存下标可以区分重复值，并判断候选何时离开窗口。
新元素至少与队尾一样大时，队尾就可以淘汰，因为新元素还会更晚过期。这样留下的值严格递减，移除过期队首后，队首就是当前最大值。每项至多入队、出队一次，所以总时间为 O(n)，队列空间为 O(k)。