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

这一课你将能做到

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;
    }
}