算法面试突击手册 —— 滑动窗口

一、概念与特点

大白话 + 类比

滑动窗口 = 毛毛虫在数组上蠕动

想象一条毛毛虫趴在数组上。它的身体（窗口）覆盖了一段连续的元素。它有两种移动方式：

尾巴缩进（左边界右移）：缩小窗口

头往前伸（右边界右移）：扩大窗口

每移动一次，它只消化新增或丢弃的一个元素，而不是重新消化整条身体里所有东西。这就是滑动窗口的威力：每次只处理增量，把 O(n²) 子数组枚举降到 O(n)。

滑动窗口和双指针的关系：滑动窗口是双指针的子集。它一定是两个指针维护一段连续区间，且右指针主导前进，左指针根据条件跟进。

固定窗口 vs 可变窗口

	固定窗口	可变窗口
窗口大小	固定（如 len(p)）	动态变化
右指针	每步必右移	每步必右移
左指针	跟在右指针后面固定步数	条件不满足时才右移（收缩）
代表题	438（异位词）、239（滑动窗口最大值）	3（最长无重复子串）、76（最小覆盖子串）
代码特征	`if (right-left+1 == k)`	`while (窗口不满足条件)`

识别信号词

“子串”、“子数组”、“连续” → 九成是滑动窗口
“最长”、“最短”、“最小覆盖” → 可变窗口求最优
“所有字母异位词”、“大小为 K 的窗口” → 固定窗口
“无重复”、“包含所有字符”、“覆盖” → 窗口内容约束

二、应用场景

滑动窗口万能模板

// 可变窗口 — 求最长合法窗口
int left = 0, maxLen = 0;
for (int right = 0; right < n; right++) {
    // 1. 加入 right 位置的元素
    window.add(s[right]);

    // 2. 当窗口不满足条件时，收缩左边界
    while (window不满足条件) {
        window.remove(s[left]);
        left++;
    }

    // 3. 此时窗口合法，更新答案
    maxLen = Math.max(maxLen, right - left + 1);
}

// 可变窗口 — 求最短覆盖窗口（76 题模式）
int left = 0, minLen = INF;
for (int right = 0; right < n; right++) {
    window.add(s[right]);

    // 当窗口满足条件时，尝试收缩找更短解
    while (window满足条件) {
        minLen = Math.min(minLen, right - left + 1);
        window.remove(s[left]);
        left++;
    }
}

三、Hot 100 精讲题目

3. Longest Substring Without Repeating Characters 无重复字符的最长子串

📌 找出字符串中不含重复字符的最长子串的长度。如 "abcabcbb" → 3（"abc"）；"pwwkew" → 3（"wke"）

🔍 解题分析

为什么用滑动窗口

要找”最长连续子串”且窗口内无重复。右指针不断扩展，遇到重复字符时左指针跳跃式收缩。

核心思路（步骤化）

用 int[128] 数组 lastPos 记录每个 ASCII 字符最近一次出现的位置
right 每次右移：读取 s[right]
关键：left = max(left, lastPos[c] + 1) —— 如果 c 在当前窗口中出现过，left 直接跳到上次出现的下一位
更新 lastPos[c] = right
更新最大长度：maxLen = max(maxLen, right - left + 1)

为什么用 Math.max(left, ...) 而不是直接跳

因为 lastPos[c] 记录的是 c 在整个字符串中的最近位置，但该位置可能已经在 left 的左边（不在当前窗口内）。用 Math.max 确保 left 只前进不后退。

优化分析：int[128] 数组替代 HashMap：

HashMap 需要 O(1) 但常数大（hash 计算、碰撞处理）
int[128] 直接用 ASCII 码做索引，是真正的 O(1) 且常数极小

关键边界条件/易错点

易错点	说明
left 不能回退	`left = Math.max(left, lastPos[c] + 1)` 用 max 保证不回退
lastPos 初始化	初始化为 -1，这样 `lastPos[c] + 1 = 0`
空字符串	循环不执行，maxLen=0，正确

手算推理：s = "abcabcbb"

right	char	lastPos 更新前	left (更新)	窗口	maxLen
0	a	lastPos[a]=-1	max(0,0)=0	[a]	1
1	b	lastPos[b]=-1	max(0,0)=0	[a,b]	2
2	c	lastPos[c]=-1	max(0,0)=0	[a,b,c]	3
3	a	lastPos[a]=0	max(0,1)=1	[b,c,a]	3
4	b	lastPos[b]=1	max(1,2)=2	[c,a,b]	3
5	c	lastPos[c]=2	max(2,3)=3	[a,b,c]	3
6	b	lastPos[b]=4	max(3,5)=5	[c,b]	3
7	b	lastPos[b]=6	max(5,7)=7	[b]	3

最终 maxLen = 3。

✅ 完整 Java 实现

public int lengthOfLongestSubstring(String s) {
    // lastPos[c]：字符 c 最近一次出现的位置（下标）
    // 初始化为 -1，表示没出现过
    int[] lastPos = new int[128];
    for (int i = 0; i < 128; i++) lastPos[i] = -1;

    int left = 0;      // 窗口左边界
    int maxLen = 0;    // 全局最长长度

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);

        // 如果 c 在当前窗口之前出现过，left 跳到那个位置的下一个
        // Math.max 确保 left 不会回退（如果出现位置已不在窗口内）
        left = Math.max(left, lastPos[c] + 1);

        // 更新 c 的最新出现位置
        lastPos[c] = right;

        // 更新答案：当前窗口长度
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

⏱ 复杂度分析

时间复杂度：O(n) —— 每个字符被访问一次，数组访问 O(1)
空间复杂度：O(1) —— int[128] 固定大小

💡 记忆口诀

“右指针只管冲，左指针跳到重复后；中间永不重复，最长记心中”

438. Find All Anagrams in a String 找到字符串中所有字母异位词

📌 在 s 中找出所有是 p 的字母异位词的子串的起始下标。异位词 = 字母组成相同但顺序可以不同。如 s="cbaebabacd", p="abc" → [0,6]

🔍 解题分析

为什么用滑动窗口

这是固定窗口的经典题。窗口大小 = p.length()，在 s 上从左滑到右。每次滑动时增量更新窗口内的字符计数，与 p 的字符计数比较。

核心思路（步骤化）

用 int[26] 数组统计 p 的字符频率（pCount）
维护另一个 int[26] 数组记录当前窗口的字符频率（winCount）
right 每步右移 → winCount 加入 s[right]
当窗口长度 == p.length() 时：
- 比较 pCount == winCount → 相同则记录 left
- 左缩：移除 s[left]，left++
继续滑动

优化判断数组相等：直接用 Arrays.equals(pCount, winCount) 比较两个长度为 26 的数组（O(26)=O(1)）。

更高端优化（可选）：维护 match 计数器。当某字符在窗口中的数量恰好等于 p 中数量时，match++；当 match == 26 或等于 p 中不同字符种类数时，记录答案。但这种优化在这里边际收益不大（26 很小）。

关键边界条件/易错点

易错点	说明
s 比 p 短	直接返回空列表
左缩的时机	先比较再左缩（当前窗口是合法的），或者先左缩再比较（如果左缩后窗口大小一致）
频率数组索引	`c - 'a'` 将字符映射到 0~25

✅ 完整 Java 实现

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    int sLen = s.length(), pLen = p.length();
    if (sLen < pLen) return result;

    int[] pCount = new int[26];  // p 的字符频率（基准）
    int[] winCount = new int[26]; // 当前窗口的字符频率

    // 初始化：统计 p 的字符频率
    for (char c : p.toCharArray()) {
        pCount[c - 'a']++;
    }

    int left = 0;
    for (int right = 0; right < sLen; right++) {
        // 右扩：窗口加入当前字符
        char rc = s.charAt(right);
        winCount[rc - 'a']++;

        // 窗口达到目标长度
        if (right - left + 1 == pLen) {
            // 判断窗口内字符组成是否与 p 完全相同
            if (Arrays.equals(winCount, pCount)) {
                result.add(left); // 找到一个异位词
            }

            // 左缩：移除左边界字符，准备向右滑动
            char lc = s.charAt(left);
            winCount[lc - 'a']--;
            left++;
        }
    }

    return result;
}

手算验证：s = "cbaebabacd", p = "abc"（pLen=3）

right	char	右扩后窗口	窗口内容	winCount == pCount?	左缩	result
0	c	[c]	c:1	—	—	—
1	b	[c,b]	b:1,c:1	—	—	—
2	a	[c,b,a]	a:1,b:1,c:1	✓	pop(c)	[0]
3	e	[b,a,e]	a:1,b:1,e:1	✗	pop(b)	[0]
4	b	[a,e,b]	a:1,b:1,e:1	✗	pop(a)	[0]
5	a	[e,b,a]	a:1,b:1,e:1	✗	pop(e)	[0]
6	b	[b,a,b]	a:1,b:2	✗	pop(b)	[0]
7	a	[a,b,a]	a:2,b:1	✗	pop(a)	[0]
8	c	[b,a,c]	a:1,b:1,c:1	✓	pop(b)	[0,6]
9	d	[a,c,d]	a:1,c:1,d:1	✗	—	[0,6]

返回 [0, 6] ✓

⏱ 复杂度分析

时间复杂度：O(n × 26) ≈ O(n) —— n 步滑动，每次比较 26 个字母 O(1)
空间复杂度：O(1) —— 两个固定大小的数组

💡 记忆口诀

“固定大小的窗口滑过去，频率数组一模一样就是异位词”

76. Minimum Window Substring 最小覆盖子串（滑动窗口最难一题）

📌 找出 s 中包含 t 所有字符的最短连续子串。如 s="ADOBECODEBANC", t="ABC" → "BANC"

🔍 解题分析

为什么是滑动窗口

要找包含所有目标字符的”最短连续子串”。这是可变窗口 + 求最短模式：

窗口不够（没覆盖全）→ 右扩
窗口够了（覆盖全了）→ 左缩（试图找更短的解）

核心思路（步骤化）

这是滑动窗口中最精巧的一题，核心在于 matched 计数器的设计：

预处理：need[128] 统计 t 中每个字符的需求量；needTypes = t 中不同字符的种类数
右扩时：
- have[s[right]]++
- 如果 have[c] == need[c]（这个字符刚好满足需求），matched++
当 matched == needTypes 时，窗口合法（所有字符都够数了）
左缩时：
- 每次左缩前先尝试更新最小窗口
- have[s[left]]--
- 如果 have[c] < need[c]（移除后不满足需求了），matched—
- left++

matched 计数器的精妙之处：不是统计”窗口里的字符总数”，而是统计”已满足需求的字符种类数”。不需要每次判断都扫描 128 个字符，只要 matched 达到 needTypes 就行。

类比：就像你在一家超市按购物清单采购。清单上有 3 种商品（needTypes=3），你推着购物车在货架间滑动。matched 记录”已经买齐了几种商品”。当 matched==3 时，意味着你可以结账了。但你可能会尝试退回一些商品（左缩），看能不能找到更短的采购路线。

关键边界条件/易错点

易错点	说明
matched 的增减条件	只在 `have[c]` 从”不够”到”刚好够”时 matched++；从”刚好够”到”不够”时 matched—
更新答案的时机	在左缩的 while 循环中，每次收缩前更新
minLen 初始值	用 `Integer.MAX_VALUE`，最后判断是否为 MAX
s 比 t 短	直接返回 ""
t 中有重复字符	`need[c] > 1` 正确处理（比如 t 中有两个 ‘A’，需要窗口中有两个 ‘A’）

手算推理：s = "ADOBECODEBANC", t = "ABC"

need: A=1, B=1, C=1, needTypes=3

right	字符	have 变化	matched	窗口	合法?	最优
0	A	A=1	1(A)	[A]	✗	—
1	D	D=1	1	[A,D]	✗	—
…	…	…	…	…	✗	—
5	C	A=1,B=1,C=1	3	[A,D,O,B,E,C]	✓	len=6
左缩	A	A→0	2(A不够)	[D,O,B,E,C]	✗	—
6	O	—	2	[D,O,B,E,C,O]	✗	—
…	…	…	…	…	…	…
9	C	A=1,B=1,C=1	3	[C,O,D,E,B,A,N,C]	✓	—
左缩	C→B	—	2→1→…	[B,A,N,C]	✓	len=4 ← 最优！

最终 s.substring(9,13) = "BANC"，长度 4。

✅ 完整 Java 实现

public String minWindow(String s, String t) {
    // s 比 t 还短，不可能覆盖
    if (s.length() < t.length()) return "";

    // need[c]：t 中字符 c 需要的数量
    int[] need = new int[128];
    int needTypes = 0; // t 中共有多少种不同字符
    for (char c : t.toCharArray()) {
        if (need[c] == 0) needTypes++; // 首次出现的字符，种类+1
        need[c]++;
    }

    // have[c]：当前窗口中字符 c 的数量
    int[] have = new int[128];
    int matched = 0; // 已满足需求的字符种类数（当 matched==needTypes 时窗口合法）

    int left = 0;
    int minStart = 0, minLen = Integer.MAX_VALUE;

    for (int right = 0; right < s.length(); right++) {
        char rc = s.charAt(right);

        // 右扩：新字符加入窗口
        have[rc]++;

        // 【关键】如果这个字符的数量刚好达到需求量，matched++
        // 注意：超过需求量不加（比如 need[A]=1，窗口有 2 个 A，只算一次满足）
        if (have[rc] == need[rc]) {
            matched++;
        }

        // 窗口合法 → 尝试收缩左边界，找更短的解
        while (matched == needTypes) {
            // 记录当前最优解
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }

            // 左缩：移除左边界字符
            char lc = s.charAt(left);
            have[lc]--;

            // 【关键】如果移除后字符数量不够了，matched--
            if (have[lc] < need[lc]) {
                matched--;
            }
            left++;
        }
    }

    return minLen == Integer.MAX_VALUE
           ? ""
           : s.substring(minStart, minStart + minLen);
}

⏱ 复杂度分析

时间复杂度：O(n) —— 每个字符最多被 right 和 left 各访问一次
空间复杂度：O(1) —— 固定大小 128 的两个数组

💡 记忆口诀

“need 定需求，have 管现状，matched 控合法性；窗口不够往右扩，够了往左缩找最短”

239. Sliding Window Maximum 滑动窗口最大值

📌 数组和窗口大小 k，返回每个窗口中的最大值。如 nums=[1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7]

🔍 解题分析

核心思路：单调递减双端队列

用一个双端队列 Deque，存下标，保证队列中下标对应的值严格递减。

单调队列三步骤：

清队尾：新元素入队前，弹出队尾所有 ≤ 当前值的下标 —— 因为它们值更小且位置更靠前，永远没机会成为最大值
入队：当前下标从队尾入队
清队头：如果队头下标已滑出窗口（deque.peekFirst() <= i - k），弹出

队头始终是当前窗口的最大值下标。

为什么是 O(n)：每个下标最多入队一次、出队一次（要么被新值挤走，要么被窗口滑走）。

类比：想象国家队的选材通道，只让身高递减的人站成一排。来了一个更高的人，前面所有比他矮的都可以回家了（因为新人更猛且更年轻，能排更久）。通道最前面站的是最高的人，如果退役了（滑出窗口），就让第二高的人顶上。

堆解法和单调队列解法对比：

	单调队列	堆
时间	O(n)	O(n log n)
空间	O(k)	O(n)
实现	需要理解单调性	更直观自然
面试	最优解，要掌握	容易想到，优先说

关键边界条件/易错点

易错点	说明
队列存下标不是值	存值无法判断是否滑出窗口
<= vs <	清队尾时用 `<=`（相同值也要弹出，留最新的位置更久的）
清队头用 if 不是 while	每步最多有一个下标滑出窗口（因为窗口每次移一格），用 if 即可
记录答案时机	窗口形成后才记录（i >= k-1）

✅ 完整 Java 实现

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    if (n == 0 || k == 0) return new int[0];

    int[] result = new int[n - k + 1]; // 结果数组

    // 双端队列：存下标，保证这些下标对应的值单调递减
    // 队头 → 最大值下标；队尾 → 最小值下标（在队列中的最小值）
    Deque<Integer> deque = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        // 步骤1：清理队尾 —— 弹出所有值 ≤ nums[i] 的下标
        // 因为它们值更小且位置更靠前，永远没机会成为窗口最大值
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
            deque.pollLast(); // 挤走不够打的
        }

        // 步骤2：当前下标入队尾
        deque.offerLast(i);

        // 步骤3：清理队头 —— 弹出已经滑出窗口的下标
        // 窗口范围：[i-k+1, i]，所以下标 ≤ i-k 的都过时了
        if (deque.peekFirst() <= i - k) {
            deque.pollFirst(); // 退役
        }

        // 步骤4：窗口形成后，队头就是当前窗口最大值
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }

    return result;
}

手算验证：nums=[1,3,-1,-3,5,3,6,7], k=3

i	num	清队尾(弹出)	入队	清队头	队列(值)	result
0	1	—	0	—	[1]	—
1	3	0(1≤3)	1	—	[3]	—
2	-1	—	2	—	[3,-1]	3
3	-3	—	3	—	[3,-1,-3]	3
4	5	3(-3≤5),2(-1≤5),1(3≤5)	4	—	[5]	5
5	3	—	5	—	[5,3]	5
6	6	5(3≤6),4(5≤6)	6	—	[6]	6
7	7	6(6≤7)	7	4?(4≤7-3)但其实4已弹出	[7]	7

窗口 4：i=6 时队列 [6]，result[4]=6。窗口 5 会清理。最终 [3,3,5,5,6,7] ✓

⏱ 复杂度分析

时间复杂度：O(n) —— 每个下标入队一次、出队最多一次
空间复杂度：O(k) —— 队列最多存 k 个下标

💡 记忆口诀

“单调队列三步走：比队尾大的挤走，自己入队，队头过期弹走”

🔜 上一章：02-双指针 | 下一章：04-前缀和

算法手册 03 滑动窗口

算法面试突击手册 —— 滑动窗口

一、概念与特点

大白话 + 类比

固定窗口 vs 可变窗口

识别信号词

二、应用场景

滑动窗口万能模板

三、Hot 100 精讲题目

3. Longest Substring Without Repeating Characters 无重复字符的最长子串

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀

438. Find All Anagrams in a String 找到字符串中所有字母异位词

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀

76. Minimum Window Substring 最小覆盖子串（滑动窗口最难一题）

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀

239. Sliding Window Maximum 滑动窗口最大值

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀