滑动窗口：连续区间的一次扫描

这一课你将能做到

1. 识别「最长 / 最短 / 连续子数组或子串满足条件」的窗口信号
2. 写出可变长度窗口的标准骨架：右指针扩张、左指针收缩、窗口内更新答案
3. 用计数数组 + 缺口计数器解决无重复最长子串和最小覆盖子串

为什么要学

上一课的双指针是两个指针独立运动，滑动窗口是它的一个高频特化：两个指针之间的区间始终代表「当前正在考察的连续子串」，右指针不断把新区间纳入，左指针在条件被破坏 / 需要找最小时把旧区间吐出。

为什么要专门学？因为「连续子数组 / 子串」问题用暴力做通常是 O(n²)（枚举每个起点和终点），而滑动窗口只扫一遍，O(n)。限流时间窗、日志统计最近 5 分钟请求、Kafka 消费速率监控，工程里的「窗口」概念也完全同源。这是中等题里模板化程度最高、投入产出比最好的一课。

先建立图像

字符串：a   b   c   a   b   c   b   b
窗口：      [-------]            ← 左右指针夹住的连续区间
           left   right
right++  → 纳入新字符，尝试扩张
left++   → 条件不满足（或找最短）时，吐出左侧字符

固定骨架（可变长度窗口）：

右指针逐格扩张
  更新窗口内的统计
  while（窗口不合法 / 还能继续收缩）：
      需要答案时先在这记录（最短类）
      左指针收缩并更新统计
  需要答案时在这记录（最长类）

口诀：求最长，合法时拼命扩张；求最短，合法时拼命收缩。

跟着做

步骤 1：LeetCode 209「长度最小的子数组」（中等，热身）

给定正整数数组和 target，找出和 ≥ target 的最短连续子数组长度，没有则返回 0。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int best = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {                 // 窗口合法，还能更短
                best = Math.min(best, right - left + 1);
                sum -= nums[left++];               // 吐掉左端，尝试缩短
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

每个元素至多进出窗口一次，时间 O(n)，空间 O(1)。这题展示「最短类」的标准动作：合法 → 记答案 → 收缩。

步骤 2：LeetCode 3「无重复字符的最长子串」（中等）

给定字符串 s，求不含重复字符的最长子串长度，如 "abcabcbb" 答案是 3（abc）。

思路：窗口 [left, right] 始终保持无重复。用计数数组记录窗口内各字符个数；右指针纳入的字符若让计数变成 2，就不断移动左指针，直到这个字符的计数回到 1。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] count = new int[128]; // ASCII
        int left = 0;
        int best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            count[c]++;
            while (count[c] > 1) {           // 新来的字符造成重复
                count[s.charAt(left)]--;
                left++;
            }
            best = Math.max(best, right - left + 1); // 窗口此刻合法
        }
        return best;
    }
}

逐点讲：注意记录答案的位置在收缩完成之后——此时窗口一定无重复。时间 O(n)（left 总共只走 n 步），空间 O(1)（128 固定大小）。

步骤 3：LeetCode 76「最小覆盖子串」（困难，窗口技巧集大成）

给定字符串 s 和 t，在 s 中找包含 t 全部字符（含个数）的最短子串，如 s="ADOBECODEBANC"、t="ABC"，答案 "BANC"。

直接模拟「窗口是否覆盖 t」每次要扫一遍计数表，代价高。引入一个 need 变量：当前窗口还缺几种字符（按「该字符个数是否达标」计，一个达标种类算一票）。右指针纳入字符时若让某字符恰好达标，need--；need 为 0 表示全覆盖，开始收缩左端找最短。

class Solution {
    public String minWindow(String s, String t) {
        int[] needCount = new int[128];
        for (char c : t.toCharArray()) needCount[c]++;

        int need = 0; // t 中出现了多少种不同字符
        for (int v : needCount) if (v > 0) need++;

        int[] have = new int[128];
        int left = 0;
        int bestStart = 0;
        int bestLen = Integer.MAX_VALUE;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            have[c]++;
            if (needCount[c] > 0 && have[c] == needCount[c]) {
                need--; // 这一种字符刚好凑够
            }
            while (need == 0) { // 已全覆盖：收缩左端求最短
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestStart = left;
                }
                char d = s.charAt(left);
                if (needCount[d] > 0 && have[d] == needCount[d]) {
                    need++; // 再删就缺这一种了
                }
                have[d]--;
                left++;
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
    }
}

逐点讲：判定「恰好达标」必须用 == 而不是 >=——多给的字符不应该重复减 need。时间 O(n)，空间 O(1)。这道是窗口类的天花板题，能独立默写，字符串窗口题就基本通关。

讲清楚要点

1. 窗口题先想「合法条件」怎么表达：和超阈值用累加变量；字符覆盖用计数表 + 缺口种类数；无重复用计数 >1。
2. 答案记录位置由最长 / 最短决定：最长在窗口合法（收缩完）后更新；最短在 while 合法内部、每次收缩前更新。
3. 右指针负责扩张，左指针负责恢复合法：两个指针总共各走 n 步，这是 O(n) 的根本原因。
4. 计数表 128 与 HashMap 的选择：ASCII 字符用数组最快；字符范围不确定（Unicode）再用 HashMap，逻辑一致。
5. 「恰好」是关键比较：凑够、超标是两件事，最小覆盖子串的 need 变化只发生在恰好达标的瞬间。

你可能会懵的地方

• 为什么双重 while 还是 O(n)？不会变 O(n²) 吗？ 看左指针总共的移动量：它在整个过程中只增不减，最多走 n 格。把所有轮次的 while 体加起来也不超过 n 次，所以整体仍是 O(n)。

• 无重复子串为什么不能用 Set 就行？ 能。遇到重复时要 while 左移并 remove，Set 也能写。计数数组更直接，因为它天然支持「重复了几个」的判断，处理含多次出现的变体（如最多含两个不同字符）也更容易扩展。

• 最小覆盖子串里 t 有重复字符（如 "AABC"）怎么办？ needCount 记录的是个数，达标条件是 have[c] == needCount[c]，重复字符天然按个数比较，不需要额外处理。

• 收缩时为什么先判 need++ 再 have--？ 要判断「删除前」是否恰好达标：若 have 正好等于 need，删完必然短缺，need++。先减再比就失去判断依据了。

• 窗口题和双指针题到底怎么区分？ 不必严格区分，窗口就是「区间有明确语义」的双指针。学习上只要记住：题目强调连续子串/子数组 + 一个关于区间的条件，优先套窗口骨架。

错法对照

错法	问题	正解
每次判断覆盖都遍历计数表	内层藏着 O(字符集)，整体退化	维护 need 缺口数，O(1) 判定
达标判断写成 have[c] >= needCount[c]	同一种字符被重复计入 need	只在 == 时变化
求最长在 while 内更新答案	取到的是收缩过程中的短窗口	收缩完成后再更新
收缩时先改 have 再判短缺	条件依据被破坏	先判定，再更新统计
用 HashMap 却忘记删 0 值键	干扰达标判断	计数用数组或允许保留 0 值

卡点急救

1. 窗口题无从下手：先写死右指针 for 循环和空的左指针，再问自己「窗口什么时候不合法」，把恢复合法的动作写进 while，骨架就立住了。
2. 最小覆盖子串 need 变来变去出错：只盯两条规则——have 从 need-1 涨到 need 时 need--；从 need 降到 need-1 时 need++。其他时刻 need 不动。
3. 答案总是差一：窗口长度统一写 right - left + 1；substring 终点是 start + len（右开）。先在纸上确认下标含义。

面试常问

• 无重复最长子串如果要求的是「至多包含 K 个不同字符」呢（LeetCode 340）？ 把 while 条件换成「窗口内不同字符种类 > K」，用一个变量维护种类数（计数从 0 变 1 时 +1），其余骨架不变。这是面试官最爱出的延展，考你是否理解条件是可插拔的。

• 滑动窗口为什么要求条件可以「增量维护」？ O(n) 的前提是加入/删除一个元素时，窗口统计能在 O(1) 更新。若条件是「窗口内元素的中位数」这类无法 O(1) 维护的量，就要配合堆等结构，单纯窗口就不够了。

• 数组里有负数时，209 题还能用窗口吗？ 不能。负数破坏「扩张窗口和一定增大、收缩一定减小」的单调性，左指针何时收缩无法判定，需要改用前缀和。能用窗口的子数组和题，默认元素为正。

自测三问

1. 求最长和求最短，更新答案分别在什么位置？为什么？
2. 最小覆盖子串的 need 变量记录的是什么？为什么能把判定降到 O(1)？
3. 举一个不能用滑动窗口的子数组问题，并说明原因。

小结一句话

滑动窗口用「右扩左缩」一次扫描搞定连续区间：合法条件能增量维护是前提，最长靠扩张、最短靠收缩，覆盖问题用缺口数代替全表检查。

延伸

• 巩固练习：LeetCode 340 至多包含 K 个不同字符的最长子串、LeetCode 567 字符串的排列、LeetCode 239 滑动窗口最大值
• 在本站在线判题平台提交时，构造 t 比 s 长、完全无解的用例检验返回值
• 下一课预告：链表——指针操作的基本功，反转、判环、合并三个必考题