双指针与滑动窗口双指针与滑动窗口
用单调移动维护区间不变量，处理子数组与字符串问题。用单调移动维护区间不变量，处理子数组与字符串问题。
专题导读
双指针通过两个单调移动的位置压缩搜索空间；滑动窗口则在双指针基础上维护一个连续区间及其统计状态。核心不是背模板，而是找到窗口条件的单调性，并明确扩张、收缩时必须保持的不变量。双指针通过两个单调移动的位置压缩搜索空间；滑动窗口则在双指针基础上维护一个连续区间及其统计状态。核心不是背模板，而是找到窗口条件的单调性，并明确扩张、收缩时必须保持的不变量。
学完本章，你应该能够
- 根据输入结构识别相向、同向和快慢指针模式根据输入结构识别相向、同向和快慢指针模式
- 区分固定窗口与可变窗口，并正确选择收缩时机区分固定窗口与可变窗口，并正确选择收缩时机
- 用计数器或哈希表 O(1) 更新窗口状态用计数器或哈希表 O(1) 更新窗口状态
- 通过指针总移动次数证明整体复杂度为 O(n)通过指针总移动次数证明整体复杂度为 O(n)
双指针模式地图双指针模式地图
双指针成立的前提通常是有序性、区间连续性，或指针移动后可以永久排除一部分候选。双指针成立的前提通常是有序性、区间连续性，或指针移动后可以永久排除一部分候选。
| 模式模式 | 指针方向指针方向 | 典型信号典型信号 | 代表问题代表问题 |
|---|---|---|---|
| 相向双指针相向双指针 | left → ← rightleft → ← right | 有序数组、两端决策有序数组、两端决策 | 两数之和、盛水容器、回文判断两数之和、盛水容器、回文判断 |
| 同向双指针同向双指针 | slow → fast →slow → fast → | 原地整理、去重、删除原地整理、去重、删除 | 移除元素、合并数组移除元素、合并数组 |
| 快慢指针快慢指针 | 不同速度同向不同速度同向 | 链表环、中点、周期链表环、中点、周期 | 环形链表、寻找中点环形链表、寻找中点 |
| 滑动窗口滑动窗口 | left → right →left → right → | 连续子数组/子串、条件单调连续子数组/子串、条件单调 | 最短覆盖、最长无重复子串最短覆盖、最长无重复子串 |
识别关键词识别关键词
题目要求连续区间，且右边界扩张会让某个指标单调增加或变差，通常可以考虑滑动窗口；如果包含负数导致区间和不再单调，应转向前缀和等方法。题目要求连续区间，且右边界扩张会让某个指标单调增加或变差，通常可以考虑滑动窗口；如果包含负数导致区间和不再单调，应转向前缀和等方法。
先写窗口不变量先写窗口不变量
可变窗口最重要的是明确：进入循环某个位置时，[left, right] 到底满足什么条件。可变窗口最重要的是明确：进入循环某个位置时，[left, right] 到底满足什么条件。
求最长合法窗口求最长合法窗口
right 每次扩张；当窗口非法时用 while 收缩直到重新合法；此时用 right-left+1 更新最大值。right 每次扩张；当窗口非法时用 while 收缩直到重新合法；此时用 right-left+1 更新最大值。
求最短合法窗口求最短合法窗口
right 扩张直到窗口合法；用 while 尽可能收缩，并在每次收缩前更新最小值。right 扩张直到窗口合法；用 while 尽可能收缩，并在每次收缩前更新最小值。
统计合法窗口数量统计合法窗口数量
若合法性具有单调性，以 right 结尾的合法区间数量通常可由当前 left 直接计算。若合法性具有单调性，以 right 结尾的合法区间数量通常可由当前 left 直接计算。
状态增量维护状态增量维护
右端进入和左端离开时只更新受影响元素，避免每次重新扫描整个窗口。右端进入和左端离开时只更新受影响元素，避免每次重新扫描整个窗口。
import java.util.HashMap;
import java.util.Map;
public final class LongestUniqueSubstring {
private LongestUniqueSubstring() {
}
public static int lengthOfLongestSubstring(String text) {
Map<Character, Integer> count = new HashMap<>();
int left = 0;
int answer = 0;
for (int right = 0; right < text.length(); right++) {
char current = text.charAt(right);
count.merge(current, 1, Integer::sum);
// 不变量：退出 while 后，窗口内没有重复字符
while (count.get(current) > 1) {
char removed = text.charAt(left++);
count.computeIfPresent(removed, (key, value) -> value - 1);
}
answer = Math.max(answer, right - left + 1);
}
return answer;
}
}
// left、right 都最多移动 n 次：时间 O(n)，空间 O(字符集)while 不会让复杂度变成 O(n²)，因为 left 在整个算法中只从 0 移动到 n，每个字符最多进入和离开窗口各一次。
固定窗口与状态更新固定窗口与状态更新
固定长度为 k 时，每轮加入 nums[right]，并在窗口超过 k 后移除 nums[right-k]，无需维护独立 left 也可以完成。固定长度为 k 时，每轮加入 nums[right]，并在窗口超过 k 后移除 nums[right-k]，无需维护独立 left 也可以完成。
public final class FixedWindow {
private FixedWindow() {
}
public static long maxWindowSum(int[] nums, int k) {
if (k <= 0 || k > nums.length) {
throw new IllegalArgumentException("k out of range");
}
long windowSum = 0L;
long answer = Long.MIN_VALUE;
for (int right = 0; right < nums.length; right++) {
windowSum += nums[right];
if (right >= k) {
windowSum -= nums[right - k];
}
if (right >= k - 1) {
answer = Math.max(answer, windowSum);
}
}
return answer;
}
}窗口达到 k 之前不要更新答案；移除元素的下标是 right-k，而不是 right-k+1。
边界、单调性与替代方案边界、单调性与替代方案
滑动窗口不是所有连续区间题的通解。只有移动边界后，合法性或目标值具有可预测变化时，才能安全排除旧状态。滑动窗口不是所有连续区间题的通解。只有移动边界后，合法性或目标值具有可预测变化时，才能安全排除旧状态。
| 问题特征问题特征 | 推荐方法推荐方法 | 原因原因 |
|---|---|---|
| 正数数组，最短和 ≥ target正数数组，最短和 ≥ target | 滑动窗口滑动窗口 | 扩张只增大和，收缩只减小和扩张只增大和，收缩只减小和 |
| 包含负数，区间和 = k包含负数，区间和 = k | 前缀和 + 哈希前缀和 + 哈希 | 加入负数后窗口和不再单调加入负数后窗口和不再单调 |
| 有序数组两数之和有序数组两数之和 | 相向双指针相向双指针 | 和过大/过小时可排除一侧和过大/过小时可排除一侧 |
| 无序数组两数之和无序数组两数之和 | 哈希表哈希表 | 没有有序性，指针移动无法排除候选没有有序性，指针移动无法排除候选 |
| 需要窗口最大值需要窗口最大值 | 单调队列单调队列 | 普通计数无法 O(1) 删除当前最大值普通计数无法 O(1) 删除当前最大值 |
常见误区
用 if 代替 while 收缩用 if 代替 while 收缩
右边界一次扩张可能导致窗口需要连续收缩多次。除非能证明每轮只需移动一次，否则应使用 while。右边界一次扩张可能导致窗口需要连续收缩多次。除非能证明每轮只需移动一次，否则应使用 while。
更新答案的时机错误更新答案的时机错误
最长合法窗口应在恢复合法后更新；最短合法窗口要在 while 内、移动 left 之前更新。最长合法窗口应在恢复合法后更新；最短合法窗口要在 while 内、移动 left 之前更新。
窗口长度 off-by-one窗口长度 off-by-one
闭区间 [left,right] 长度是 right-left+1；半开区间 [left,right) 长度才是 right-left。全篇保持统一。闭区间 [left,right] 长度是 right-left+1；半开区间 [left,right) 长度才是 right-left。全篇保持统一。
忽略条件单调性忽略条件单调性
数组含负数时，窗口和随边界移动不再单调，传统滑动窗口可能漏解。数组含负数时，窗口和随边界移动不再单调，传统滑动窗口可能漏解。
面试追问延伸思考
为什么滑动窗口是 O(n) 而不是 O(n²)？为什么滑动窗口是 O(n) 而不是 O(n²)？
虽然代码中 for 内有 while，但 left 与 right 都只单调向右，每个元素最多进入、离开窗口各一次，总指针移动次数不超过 2n。虽然代码中 for 内有 while，但 left 与 right 都只单调向右，每个元素最多进入、离开窗口各一次，总指针移动次数不超过 2n。
什么时候不能使用滑动窗口？什么时候不能使用滑动窗口？
当移动边界后窗口条件没有单调变化，无法证明被移除状态不可能成为答案时不能使用。例如含负数数组的区间和问题通常改用前缀和与哈希。当移动边界后窗口条件没有单调变化，无法证明被移除状态不可能成为答案时不能使用。例如含负数数组的区间和问题通常改用前缀和与哈希。
最长窗口和最短窗口的模板有什么区别？最长窗口和最短窗口的模板有什么区别？
最长问题在窗口非法时收缩，恢复合法后更新最大值；最短问题先扩张到合法，然后在合法期间不断更新答案并收缩，寻找更短区间。最长问题在窗口非法时收缩，恢复合法后更新最大值；最短问题先扩张到合法，然后在合法期间不断更新答案并收缩，寻找更短区间。