专题 03滑动窗口

3.1从暴力 O(n²) 到 O(n)

先看清暴力解为什么慢，才知道滑窗省掉了什么。以「找和 ≥ target 的最短子数组」为例，暴力思路是：

for (int i = 0; i < n; i++)          // 左边界
    for (int j = i; j < n; j++)      // 右边界
        检查 nums[i..j] 是否满足条件

i 和 j 各自能往前往后乱走，组合出 O(n²) 个子段。但注意一个事实： 子段 [i, j] 和 [i, j+1] 只差一个元素，我们却每次都从头重新算一遍和——大量重复劳动。

关键观察：两个边界都「只前进、不回头」

能不能让 right 一直往右走，left 也一直往右走，谁也不后退？

• 右指针只前进：不断把新元素「纳入窗口」，直到窗口满足条件（比如和够了）。
• 左指针只前进：窗口一旦满足条件，就尝试把左边元素「踢出去」来缩小窗口，看能不能仍满足条件且更短/更优。

因为两个指针都不回头，每个元素最多被「进窗口」和「出窗口」各一次，总操作 O(n)。 这就是滑动窗口的核心：用「两个只前进的指针 + 维护窗口状态」，替代「枚举所有子段」。

3.2滑动窗口通用模板

下面这个骨架，本章四道题都能往上套。务必理解到能默写。先给带注释的通用版，再讲两种变体。

// 通用骨架（以「在序列里找满足条件的连续子段」为例）
int left = 0;            // 窗口左边界
// windowState 记录当前窗口的状态（和 / 频次 / 是否达标等）
for (int right = 0; right < n; right++) {
    // ① 右扩：把 nums[right] 纳入窗口，更新窗口状态
    纳入 nums[right];

    // ② 判断：窗口是否满足条件
    while (窗口满足条件) {
        // ③ 收缩：尝试把 left 右移，缩小窗口
        更新答案(可能);     // 求最短/最长在这里记录
        把 nums[left] 移出窗口，更新窗口状态;
        left++;
    }
    // 若求最长，有时在 ② 之外（窗口非法时）也更新答案，见下文变体
}

变体一：求「最短」子段（满足条件里挑最短）

典型：和 ≥ target 的最小子数组、最小覆盖子串。套路是「满足条件就收缩」： while (满足条件) 里不断踢左边界，每踢一次都可能是更短的答案，所以在收缩循环内更新答案。 收缩到「刚好不满足」为止，再扩右边界。

变体二：求「最长」子段（不满足条件里挑最长）

典型：无重复字符的最长子串。套路是「不满足（出现重复）就收缩」： 窗口一旦非法（出现了重复字符），就踢左边界直到重新合法；每次窗口合法时更新答案（在收缩循环外， 因为合法窗口本身就是候选最长）。

3.3长度最小的子数组（中等，力扣 209）

中等 核心：求最短变体 · 正数数组

题意：给定只包含正整数的数组 nums 和正整数 target， 找出和 ≥ target 的连续子数组的最小长度；若不存在返回 0。 例：nums = [2,3,1,2,4,3], target = 7，子数组 [4,3] 和为 7、长度 2，是最小，返回 2。

思路推导

第一步，暴力。枚举所有子段求和，O(n²)。

第二步，为什么滑窗能用——正数数组的单调性。因为元素都 > 0，右边界右移 → 窗口和必增；左边界右移 → 窗口和必减。 这个单调性让「窗口和」随指针移动方向确定，从而能放心地「够了就缩、不够就扩」。

第三步，套「求最短」模板。right 不断把元素加进窗口、累加和；一旦 sum >= target， 就记录当前长度，并在 while 里收缩左边界（先减去将移出的元素再 left++），看能不能更短还满足。 收缩到 sum < target 后，继续扩右边界。

为什么 left 右移不会漏掉更优解？对于当前已 ≥ target 的窗口，更短且仍 ≥ target 的窗口只可能在它内部 （左边界更靠右）。所以放心收缩；一旦缩到不满足，说明当前 left 下再短就不可能满足了，必须扩 right——此时再回头缩 left 没意义，因为那会丢元素、更不满足。两指针都只前进，O(n)。

参考代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, sum = 0;
        int ans = Integer.MAX_VALUE;          // 记录最短长度，初始为「无穷大」
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];               // ① 右扩：新元素进窗口
            while (sum >= target) {           // ② 满足就收缩（求最短）
                ans = Math.min(ans, right - left + 1); // 更新最短长度
                sum -= nums[left];            // ③ 收缩前，先减去将移出的元素
                left++;
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans; // 没找到任何满足条件的，返回 0
    }
}

复杂度

O(n) 时间（right、left 各最多走 n 步），O(1) 空间（只用几个变量）。注意：只适用于正数/非负数组，见 3.7 节坑一。

3.4无重复字符的最长子串（中等，力扣 3）

中等 核心：求最长变体 · 数组记上次位置

题意：给定字符串 s，找出不含重复字符的最长子串的长度。 例：s = "abcabcbb" → 最长无重复子串是 "abc"，返回 3；s = "bbbbb" → "b"，返回 1。

思路推导

第一步，暴力。枚举所有子串、逐个查是否含重复，O(n³) 或 O(n²)，太慢。

第二步，滑窗维护「无重复」。维护窗口 [left, right] 始终无重复。right 右扩时加入 s[right]： 若它已经在窗口里出现过（重复），就必须把 left 右移到「那个重复字符的下一个位置」，让窗口重新无重复。 每次窗口合法，就更新最长长度。

第三步，用数组 O(1) 找「上次出现位置」。怎么快速知道 s[right] 上次在哪、是否还在窗口内？ 用 int[128] 记每个字符最近一次出现的下标（ASCII 足够）。 规则：若 last[c] >= left，说明 c 在当前窗口里出现过，令 left = last[c] + 1（跳到重复字符之后）； 然后更新 last[c] = right。这比「逐个 left++ 直到不重复」更直接，一步定位。

参考代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] last = new int[128];           // 记录每个字符最近出现下标
        Arrays.fill(last, -1);               // 初始 -1 表示还没出现过
        int left = 0, ans = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            // 若 c 在窗口里出现过（上次位置 >= left），left 跳到它后面
            if (last[c] >= left) {
                left = last[c] + 1;
            }
            last[c] = right;                 // 更新 c 的最新位置
            ans = Math.max(ans, right - left + 1); // 窗口合法，更新最长
        }
        return ans;
    }
}

复杂度

O(n) 时间（right 走一遍，left 只增），O(1) 空间（128 长度固定数组）。这是「求最长」变体的标准写法。

3.5找到字符串中所有字母异位词（简单，力扣 438）

简单 核心：固定窗口 · 双计数数组

题意：给定字符串 s 和 p，找出 p 的所有字母异位词在 s 中的起始下标。 例：s = "abab", p = "ab" → 异位词出现在下标 0("ab")、1("ba")、2("ab")，返回 [0, 1, 2]。

思路推导

第一步，暴力。枚举 s 所有长度 = p.length() 的子串，逐个判断是否异位词，O(n·k²) 量级。

第二步，固定窗口 + 频次比较。p 的异位词长度一定等于 p.length()，所以窗口大小固定为 plen。 用 int[26] 数组 need 记 p 的频次；用 win 记当前窗口频次。当窗口长度达到 plen 时， 若 win 与 need 完全一致，则该窗口是 p 的异位词，记下左边界。

第三步，滑起来：进一个、出一个。right 右移把 s[right] 加进 win；一旦窗口长度超过 plen， 就把「刚滑出左边界的元素」s[right - plen] 从 win 减掉，保持窗口恒为 plen。这样每步只做 O(1) 的频次增减， 到长度恰为 plen 时用 Arrays.equals(win, need) 判等（O(26) 常数）。

为什么只看长度 = plen 的窗口？因为异位词必须长度和字符频次都一致；长度不一直接排除，长度一致再比频次，恰好完整覆盖「是异位词」的充要条件。

参考代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) return res;     // s 比 p 还短，不可能有
        int[] need = new int[26];
        int[] win = new int[26];
        for (char c : p.toCharArray()) need[c - 'a']++; // p 的频次
        int plen = p.length();
        for (int right = 0; right < s.length(); right++) {
            win[s.charAt(right) - 'a']++;             // 右端字符进窗口
            if (right >= plen) {                       // 窗口超长，左端字符移出
                win[s.charAt(right - plen) - 'a']--;
            }
            if (right >= plen - 1) {                   // 窗口刚好 plen 长，检查
                if (Arrays.equals(win, need)) {
                    res.add(right - plen + 1);        // 记录起始下标
                }
            }
        }
        return res;
    }
}

复杂度

O(n) 时间（right 走一遍，每步 O(26) 常数频次操作），O(1) 空间（两个 26 长数组）。这是「固定窗口」变体的范例。

3.6最小覆盖子串（困难，力扣 76）

困难 核心：求最短变体完整形态 · need/window 计数

题意：给定字符串 s 和 t，在 s 中找出能覆盖 t 所有字符（含频次）的最短子串； 若没有返回空串。 例：s = "ADOBECODEBANC", t = "ABC" → 最短覆盖子串是 "BANC"，返回它。

思路推导

第一步，套「求最短」模板。维护窗口 [left, right]，目标是让窗口「覆盖 t」。right 扩、left 在满足时缩，找最短。

第二步，怎么算「覆盖了 t」。用 need[128] 记 t 的频次，win[128] 记窗口频次。 但「每步比对整个数组是否包含 t」太慢。改进：用 valid 记录「频次已达标」的字符种类数。 只有某字符在窗口里的频次刚好达到它在 t 里的频次时，valid 才 +1。 当 valid == t 中不同字符的种类数，说明窗口已覆盖 t，可以收缩求最短。

第三步，收缩时别忘了回退 valid。left 右移踢出字符 d 前，若 win[d] 当时恰好等于 need[d]， 说明这一踢会让 d 不再达标，valid 要 -1；再执行 win[d]--。顺序不能反（先判再减）。

参考代码

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        int[] win = new int[128];
        int needCnt = 0;                        // t 中不同字符的种类数
        for (char c : t.toCharArray()) {
            if (need[c]++ == 0) needCnt++;      // 首次出现某字符，种类数 +1
        }
        int left = 0, valid = 0;                // valid：窗口中「频次已达标」的字符种类数
        int start = 0, minLen = Integer.MAX_VALUE;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (need[c] > 0) {                  // 只关心 t 里出现的字符
                win[c]++;
                if (win[c] == need[c]) valid++; // 该字符频次刚达标
            }
            while (valid == needCnt) {          // 已覆盖 t，收缩求最短
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;  // 记录当前最短
                    start = left;
                }
                char d = s.charAt(left);
                if (need[d] > 0) {
                    if (win[d] == need[d]) valid--; // 即将移出导致不达标，先减 valid
                    win[d]--;                    // 再真正移出
                }
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

复杂度

O(n) 时间（两指针各走一遍，每步 O(1) 频次操作），O(1) 空间（128 定长数组）。困难题，但骨架和 3.3 完全一致，只是状态维护更细。

3.7本专题常见坑

3.8自测题