S03-X07 · 滑动窗口与双指针：一类问题的统一套路

"求最长无重复字符子串"和"有序数组里找两数之和"，一个求区间、一个找配对，暴力解都是两层循环，正解却都用两个下标，且每个下标只朝一个方向走。能不能归到同一类，取决于两个特征：答案是否为原数组的一段连续区间、扩张与收缩时判断条件是否单调。

下面把套路压成四步：判断能不能用 → 选哪种指针形态 → 套骨架 → 校验边界。

1. 什么题能用：一张清单

特征	满足	不满足（用不了）
答案形态	原数组的连续区间 `[left, right]`	子序列、任意组合、只要下标对
单调性	右界扩张后条件只会更松或更紧，可预测	条件来回震荡，扩张后要回头
目标	最长 / 最短 / 是否存在 / 计数	枚举全部方案、全局最优
数据	元素非负时和与积单调	含负数，和不再随窗口扩大而变化

三个典型反例：

最长递增子序列：子序列不连续，[left, right] 表达不了，只能 dp 或贪心+二分；
0-1 背包：要的是全局最值加容量维度，没有"区间"这回事；
无序数组的两数之和：没有单调性，只能拿 HashMap 换空间。

清单过不了就别硬套窗口，硬套只会得到"能过样例"的错误解。

2. 四种变体：一个骨架，三处不同

// 四种变体共用外层循环，差别只在何时收缩、按什么收缩、答案记在哪
int left = 0, ans = 0;
int[] window = new int[128];
for (int right = 0; right < n; right++) {
    window[s.charAt(right)]++;            // 扩张：纳入 right，一次只保留一个分支

    // A｜固定长度 k：超长就吐一个，窗口恒为 k
    if (right - left + 1 > k) window[s.charAt(left++)]--;

    // B｜变长求最长：不合法就吐，吐到重新合法，再记答案
    while (invalid(window)) window[s.charAt(left++)]--;
    ans = Math.max(ans, right - left + 1);

    // C｜变长求最短：合法就收缩，边缩边记，先记后吐
    while (valid(window)) {
        ans = Math.min(ans, right - left + 1);
        window[s.charAt(left++)]--;
    }

    // D｜计数型：长度恒为 k，每步只累加一次判定
    if (right - left + 1 == k && valid(window)) count++;
}

变体	收缩时机	答案更新时机	典型题
A 固定长度	循环内 `if`	循环末尾	长度 k 的子数组最大平均值
B 求最长	`while` 不合法	收缩之后	无重复字符的最长子串
C 求最短	`while` 合法	收缩之前	和 ≥ target 的最短子数组
D 计数	长度恒为 k	判定通过即累加	找到所有字母异位词

B 与 C 的答案位置正好相反：最长在收缩干净之后，最短在收缩开始之前，写反就差一个元素。

3. 统一骨架：扩张右界 + 收缩左界

int left = 0;
for (int right = 0; right < n; right++) {
    add(s[right]);                 // 1) 扩张：把 right 纳入状态
    while (needShrink()) {         // 2) 收缩：不满足就一直吐
        remove(s[left]);
        left++;
    }
    ans = Math.max(ans, right - left + 1);   // 3) 此刻窗口必然合法
}

总代价是 O(n) 而不是 O(n²) 的原因：

right 每轮前进 1，走满 n 步；
left 只增不减，最多从 0 走到 n；
内层 while 每迭代一次 left 就加 1，所以内层总迭代次数不超过 n，与外层可加，总操作量约 2n。

前提只有一条：收缩不能让已经合法的部分变回不合法，否则 left 会被迫回退，均摊分析失效。这就是"单调性"那条清单项的实际含义。

4. 双指针三形态

形态	移动方式	适用条件	典型题
对撞	`left++` / `right--` 向中间收	有序，或可从两端排除	两数之和、回文串、盛水容器
同向快慢	`slow` 写、`fast` 读，`slow ≤ fast`	原地删除、去重、压缩	移除元素、删除有序数组重复项
分离（窗口）	两指针同向，维护 `[left, right]`	连续区间 + 单调性	最长无重复子串、最短覆盖子串

对撞是每次比较排除一端；快慢是用写指针卡住已处理区的边界；滑动窗口是快慢的特例，只是多维护了一份窗口状态。

5. 两数之和与三数之和

// 有序数组的两数之和：每步必然排除一个候选，O(n)
int i = 0, j = nums.length - 1;
while (i < j) {
    int sum = nums[i] + nums[j];
    if (sum == target) return new int[]{i, j};
    if (sum < target) i++;    // 和太小，i 右移才可能变大
    else j--;                 // 和太大，j 左移才可能变小
}

// 三数之和：排序 + 固定一个数 + 内层对撞，整体 O(n²)
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] == nums[i - 1]) continue;   // 外层去重：与前一个位置比
    int l = i + 1, r = nums.length - 1;
    while (l < r) {
        int sum = nums[i] + nums[l] + nums[r];
        if (sum < 0) l++;
        else if (sum > 0) r--;
        else {
            res.add(List.of(nums[i], nums[l], nums[r]));
            while (l < r && nums[l] == nums[l + 1]) l++;   // 先记录，再连续跳
            while (l < r && nums[r] == nums[r - 1]) r--;
            l++; r--;                                      // 跳过本次命中
        }
    }
}

去重只有一条规则：和已经处理过的位置比，不和本次的值比。内层在命中并移动之后连续跳过；漏掉跳过会重复收集，把跳过放到移动之前会漏解。

6. 从 `O(n²)` 到 `O(n)` 的代价

换来的能力	前提	手段
对撞把两重循环压成一重	有序	排序 `O(n log n)`，或 `HashMap` 换 `O(n)` 空间
窗口状态 O(1) 更新	增量可逆（加得上也减得回）	`int[128]` / `HashMap` 频率表
区间和 O(1)	前缀和可相减	`prefix[right+1] - prefix[left]`
窗口最值 O(1)	单调队列	双端队列存下标，队首过期即弹
降不下去	无序 + 精确枚举所有组合 + 条件不单调	只能 `O(n²)` 或 `O(2^n)` 枚举

n = 10^5 时，O(n²) 是 10^10 级操作，O(n) 是 10^5 级，这是典型量级上的分水岭，与机器快慢无关。条件不单调时，任何窗口写法都只是把错误答案算得更快。

7. 最短覆盖子串：细节全在顺序里

int[] need = new int[128], window = new int[128];
for (char c : t.toCharArray()) need[c]++;
int left = 0, valid = 0, start = 0, len = Integer.MAX_VALUE;

for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    window[c]++;
    if (need[c] > 0 && window[c] == need[c]) valid++;   // 只统计 t 里有的字符

    while (valid == required) {                         // 已覆盖，尝试变短
        if (right - left + 1 < len) { len = right - left + 1; start = left; }
        char d = s.charAt(left++);
        if (need[d] > 0 && window[d] == need[d]) valid--;  // 先判后减，反了就错
        window[d]--;
    }
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);

四个必须守住的点：

valid 只在 need[c] > 0 时更新，否则窗口里多出的无关字符会把计数撑爆；
收缩时判断 window[d] == need[d] 必须在 window[d]-- 之前，减完就永远不相等；
记录答案必须在收缩之前，这一刻 [left, right] 才是覆盖窗口；
用 start + len 记结果，别在循环里 substring，否则每次收缩多一次拷贝。

总代价 O(|s| + |t|)，空间 O(128) 常数。

8. 排错

现象	原因	处理
答案偶尔偏大	收缩写成 `if` 而非 `while`	一步只退一格，必须循环到条件翻转
最短类答案差 1	先收缩再记答案	最短先记后缩，最长先缩后记
空数组 / 单元素崩	`right - left + 1` 仍在执行	入口 `if (n == 0) return ...`
后一轮结果被污染	窗口计数没回滚	`left++` 的同时必须从 `window` 减掉移出元素
中文 / emoji 直接崩	`int[128]` 只覆盖 ASCII	换 `HashMap<Character, Integer>` 或按码点走
三元组重复	去重比"值相等"而非"与前一个位置比"	外层比 `nums[i-1]`，内层移动后再跳

第 5 条在 JDK 17 上不是结果错，是 ArrayIndexOutOfBoundsException：char 是 UTF-16 码元，任何大于 127 的字符直接越界。

9. 边界

输入	正确行为	易错点
`n = 0` / `s = ""`	返回空串或 0	循环不进入，答案初值要能表达"无解"
`k > n`（固定长度）	返回 0	`right - left + 1 > k` 永不成立，窗口一路变长
全相同字符 `"aaaa"`	最长返回 `n`，最短返回 1	去重逻辑把整段跳空
`target` 不存在	返回空，不抛异常	对撞走到 `i >= j` 自然退出
`t` 比 `s` 长	立即返回空串	不进循环，`len` 停在 `Integer.MAX_VALUE`
含负数的和类窗口	换前缀和 + `HashMap`	加负数会让和变小，窗口不再单调

最后一条值得记住：和类问题一旦出现负数，滑动窗口的前提就没了，标准替代是前缀和配哈希表——prefix[j] - prefix[i] == k 转成"查 prefix[j] - k 是否出现过"。

10. 自测

一个题宣称用滑动窗口，但数组含负数，你会先质疑它哪一步？
求最长时答案更新为什么必须放在内层 while 之后？
left 只增不减是 O(n) 的关键，若允许 left 回退，均摊分析会变成什么？
三数之和的内层去重，比较对象为什么必须是相邻位置而不是本次命中的值？
最短覆盖子串里 valid 为什么不能对所有字符都加一？
有序数组的两数之和改成无序输入，O(n) 还保得住吗，代价是什么？