03 最小覆盖子串：可变窗口收缩条件的黄金法则

最小覆盖子串：可变窗口收缩条件的黄金法则

摘要

可变窗口是滑动窗口中难度的核心所在，而最小覆盖子串（LeetCode 76）是可变窗口中公认的经典难题之一。本文以 LeetCode 3（无重复字符的最长子串）作为热身引入，再深入解析 LeetCode 76 的完整思维链：如何定义”窗口合法”、何时触发收缩、need/have 双计数器的设计逻辑、以及面试中最容易出错的几个细节。本文的重点不是给你背一段代码，而是让你真正理解为什么这样写——这样即使换了一道类似题，你也能举一反三。

---

第 1 章 可变窗口的核心挑战：什么时候收缩

1.1 回顾固定窗口与可变窗口的根本差异

固定窗口的左指针跟着右指针同步移动，无需思考”何时移动左指针”——每次右指针前进一步，左指针也前进一步，窗口大小不变。

可变窗口没有这个简便条件。左指针什么时候移动？移动多少步？这两个问题是可变窗口的全部难点，也是面试考察的重点。

一个典型的错误理解：很多初学者认为，可变窗口左指针每次也只移动一步，只是移动的条件不同。这个理解不够准确——左指针可能一次连续移动多步，直到窗口从”不合法”变为”合法”为止。

1.2 合法性的单调性假设

可变窗口能正确工作，依赖一个关键的单调性假设：

如果当前窗口 $[l,r]$ 不合法（条件违反），那么将右端点固定为 $r$，向右移动左端点（即收缩左边界），一定能在某个位置使窗口重新合法。

这意味着：对于固定的右端点，窗口的”合法性”关于左端点是单调的——左端点越小，窗口越”宽”（包含更多元素），越可能违反条件；左端点越大，窗口越”窄”，越可能满足条件（或者说，越可能”恢复”）。

对于”最小覆盖”和”最长无重复”这两类问题，这个假设都成立：

• 无重复字符：去掉左边的一个字符，不会引入新的重复（只可能消除重复）
• 覆盖目标字符集：加入右边的字符可能让覆盖更完整，去掉左边的字符可能让覆盖不足

1.3 “最长”与”最短”问题的解法结构对称性

可变窗口有两种方向：

求最长合法窗口（如无重复字符最长子串）：

• 条件：窗口合法时尽量扩大（右指针前进）
• 收缩条件：窗口不合法时收缩（左指针前进）
• 答案更新：在收缩之后（窗口刚好合法时）记录当前窗口大小

求最短合法窗口（如最小覆盖子串）：

• 条件：窗口合法时记录答案，然后尝试收缩（看能否找到更短的合法窗口）
• 收缩条件：窗口合法时收缩（左指针前进）
• 答案更新：在收缩之前（窗口合法时）记录当前窗口大小

这两种方向的 while 循环条件恰好相反：一个是”不合法时收缩”，一个是”合法时收缩”。

---

第 2 章 热身：LeetCode 3 无重复字符的最长子串

2.1 题目

LeetCode 3 - Longest Substring Without Repeating Characters（中等）

给定一个字符串 s，请找出其中不含有重复字符的最长子串的长度。

输入：s = "abcabcbb"
输出：3，解释："abc" 是最长的无重复字符子串，长度为 3

输入：s = "bbbbb"
输出：1，解释：只有 "b" 能满足条件，长度为 1

输入：s = "pwwkew"
输出：3，解释："wke" 是最长的无重复字符子串

2.2 暴力分析

枚举所有子串 $O(n^2)$，每次检查是否有重复字符 $O(n)$，总体 $O(n^3)$。用集合辅助可以 $O(1)$ 检查重复，但枚举仍是 $O(n^2)$。

2.3 滑动窗口思路

窗口含义：$[left,right]$ 内的字符没有重复。

进窗：右指针向右扩展，s[right] 进入窗口。

收缩条件：进入 s[right] 后，如果窗口内出现重复（s[right] 在 $[left,right-1]$ 中已存在），就需要收缩左边界，直到重复消失。

答案更新：每次窗口合法（没有重复）时，更新最大窗口大小。

public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    int left = 0, maxLen = 0;
    // 字符 → 最近出现位置的映射
    // 用 HashMap 而不是 int[128] 是因为题目说输入可能包含所有 ASCII 字符
    Map<Character, Integer> lastPos = new HashMap<>();
 
    for (int right = 0; right < n; right++) {
        char c = s.charAt(right);
        // 如果 c 在窗口内已出现（lastPos 中记录的位置 >= left），需要收缩
        if (lastPos.containsKey(c) && lastPos.get(c) >= left) {
            left = lastPos.get(c) + 1;  // 直接跳到重复字符的下一位，一步到位
        }
        lastPos.put(c, right);           // 更新 c 的最近出现位置
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

注意：这里的收缩是”直接跳”（left = lastPos.get(c) + 1）而不是”逐步移动”（while 循环），因为我们记录了每个字符最近出现的位置，可以直接算出最少需要把左边界移动到哪里才能消除重复。

核心概念：直接跳与逐步收缩的等价性

直接跳 left = lastPos.get(c) + 1 等价于用 while 循环逐步移动 left 直到 s[left-1] == c 的结果，但时间复杂度从均摊 $O(n)$ 优化成了每步 $O(1)$。这个优化只在”我们知道确切的收缩终点”时适用，在更复杂的场景（如最小覆盖子串）中，收缩终点不确定，只能用 while 循环。

2.4 为什么用 lastPos.get(c) >= left 而不是 lastPos.containsKey(c)

lastPos 中记录的是字符全局最近出现位置，而当前窗口是 $[left,right]$。如果某个字符最近出现在 $left$ 的左边（即已经不在窗口内了），就不应该触发收缩。

示例：s = "abba"
处理到 right=3（字符 'a'）时：
  lastPos['a'] = 0（最近出现在 index 0）
  当前 left = 2（上一步因为重复的 'b' 移动到了 2）
  lastPos['a'] = 0 < left = 2，说明 'a' 不在当前窗口内，不需要收缩

如果不加 >= left 的检查，就会错误地将 left 收缩到 1，导致窗口 [1, 3] = “bba” 被认为有重复，实际上正确窗口应该是 [2, 3] = “ba”。

---

第 3 章 LeetCode 76：最小覆盖子串

3.1 题目

LeetCode 76 - Minimum Window Substring（困难）

给你一个字符串 s 和一个字符串 t，返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。

注意：对于 t 中重复字符，我们寻找的子串中该字符数量必须不少于 t 中该字符的数量。

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释："BANC" 是包含 A、B、C 的最短子串

输入：s = "a", t = "a"
输出："a"

输入：s = "a", t = "aa"
输出：""，因为 s 中没有两个 'a'

3.2 问题的核心难点

这道题有几个层次的难度：

难点一：t 中有重复字符。不是简单地”窗口内包含 t 中的所有字符种类”就够了，还需要每种字符的数量都不少于 t 中的数量。

难点二：如何高效判断”窗口是否覆盖 t”。暴力判断需要 $O(|\Sigma |)$ 时间，用计数器优化到 $O(1)$。

难点三：求最短（而不是最长）。答案更新的时机与最长窗口相反。

3.3 核心设计：need/have 双计数器

设计思路：

用两个哈希表：

• need：t 中每个字符需要出现的次数（目标频率，固定不变）
• window：当前窗口中每个字符出现的次数（动态更新）

用两个整数：

• formed：当前窗口中已经满足需求的字符种类数（window[c] >= need[c] 的字符 c 的数量）
• required：t 中不同字符的种类总数（目标，固定不变）

当 formed == required 时，窗口”覆盖”了 t。

为什么用字符种类数而不是字符总数？

字符总数判断容易误判：如果 t = "AA"，need['A'] = 2。当窗口有 3 个 ‘A’ 时，总数是 3，但已满足 t 的需求（需要 2 个，有 3 个，超额满足）。用种类数结合”当 window[c] 从 need[c]-1 增加到 need[c] 时，formed++”的逻辑，可以精确捕捉”恰好满足”的时刻。

3.4 完整代码实现

public String minWindow(String s, String t) {
    if (s.isEmpty() || t.isEmpty()) return "";
 
    // 统计 t 中每个字符的需求量
    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) {
        need.merge(c, 1, Integer::sum);  // need.put(c, need.getOrDefault(c,0)+1)
    }
 
    int required = need.size();  // t 中不同字符的种类数
 
    int left = 0;
    int formed = 0;              // 当前窗口中已满足需求的字符种类数
    Map<Character, Integer> window = new HashMap<>();
 
    // 记录最优答案：[窗口长度, 左端点, 右端点]
    int[] best = {Integer.MAX_VALUE, 0, 0};
 
    for (int right = 0; right < s.length(); right++) {
        // 步骤 1：右端点字符进窗
        char c = s.charAt(right);
        window.merge(c, 1, Integer::sum);
 
        // 步骤 2：检查刚进窗的字符是否让某种字符"恰好满足"
        if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) {
            formed++;
        }
 
        // 步骤 3：当所有字符都满足时（formed == required），尝试收缩窗口
        while (formed == required && left <= right) {
            // 记录当前窗口作为候选答案
            int windowLen = right - left + 1;
            if (windowLen < best[0]) {
                best[0] = windowLen;
                best[1] = left;
                best[2] = right;
            }
 
            // 尝试收缩：左端点字符出窗
            char outChar = s.charAt(left);
            window.merge(outChar, -1, Integer::sum);
 
            // 检查出窗字符是否破坏了某种字符的满足状态
            if (need.containsKey(outChar) && window.get(outChar) < need.get(outChar)) {
                formed--;  // 该字符不再满足，formed--
            }
            left++;
        }
    }
 
    return best[0] == Integer.MAX_VALUE ? "" : s.substring(best[1], best[2] + 1);
}

时间复杂度：$O(|s|+|t|)$（每个字符各进出窗口一次） 空间复杂度：$O(|\Sigma |)$（字符集大小，最多 52 个字母）

3.5 逐行解析：每个设计决策的理由

为什么用 window.get(c).intValue() == need.get(c).intValue() 而不是 window.get(c) == need.get(c)？

Java 的 Integer 对象在值大于 127 时不使用缓存，== 比较的是对象引用，可能返回 false（即使值相同）。必须用 .intValue() 或 .equals() 进行值比较。这是 Java 特有的陷阱。

while 循环内为什么先记录答案，再出窗？

因为”合法”是收缩的触发条件，进入 while 循环时窗口一定合法，此时窗口是当前 right 下的一个合法候选。记录答案后，再尝试将 left++ 缩小窗口，看是否能找到更短的合法窗口。

如果先出窗再记录答案，此时窗口已经可能不合法，记录的是无效答案。

left <= right 的条件是否必要？

是的，防止 left 超过 right。理论上，当 formed == required 时，窗口至少包含 t 的所有字符，left 不应该能超过 right（除非 t 是空串，但这已在开头处理）。加上这个条件是防御性编程。

生产避坑：Java Integer 的 == 比较陷阱

Java 中，Integer 对象的 == 只在值 $[-128,127]$ 范围内可靠（因为这个范围有 Integer 缓存）。字符频率超过 127 的场景虽然极少，但写代码时应养成用 .equals() 或 .intValue() 比较 Integer 的习惯，避免隐式 bug。

3.6 优化：用 int[] 替代 HashMap

题目说 s 和 t 只包含大写和小写英文字母，字符集固定为 52 个字符，可以用 int[128]（覆盖所有 ASCII 字符）替代 HashMap，避免装箱/拆箱的开销：

public String minWindow(String s, String t) {
    int[] need = new int[128];    // need[c] = t 中字符 c 的需求量
    int[] window = new int[128];  // window[c] = 当前窗口中字符 c 的数量
 
    int required = 0;
    for (char c : t.toCharArray()) {
        if (need[c] == 0) required++;  // 新字符种类出现
        need[c]++;
    }
 
    int left = 0, formed = 0;
    int bestLen = Integer.MAX_VALUE, bestLeft = 0;
 
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        window[c]++;
        if (need[c] > 0 && window[c] == need[c]) formed++;
 
        while (formed == required) {
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestLeft = left;
            }
            char out = s.charAt(left++);
            if (need[out] > 0 && window[out] == need[out]) formed--;
            window[out]--;
        }
    }
 
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestLeft, bestLeft + bestLen);
}

这个版本的代码更简洁、性能更好，面试中也更推荐。

3.7 追踪示例：验证思路

用 s = "ADOBECODEBANC", t = "ABC" 手动追踪：

right	进窗字符	window	formed	操作	best
0	A	{A:1}	1	—	∞
1	D	{A:1,D:1}	1	—	∞
2	O	{A:1,D:1,O:1}	1	—	∞
3	B	{A:1,B:1,D:1,O:1}	2	—	∞
4	E	…	2	—	∞
5	C	{A:1,B:1,C:1,…}	3	合法！收缩 left	长度 6 “ADOBEC”
5	left=A→1	…	3	继续收缩	—
5	left=D→2	…	3	继续收缩	—
5	left=O→3	…	3	继续收缩	—
5	left=B→4	B不够了	2	停止	长度 6
…	…	…	…	…	…
12	C	{A:1,B:1,C:1,…}	3	合法！收缩	最终 “BANC” 长度 4

---

第 4 章 两题对比：最长 vs 最短的解法镜像

4.1 代码结构对比

要素	LeetCode 3（最长无重复）	LeetCode 76（最小覆盖）
窗口含义	无重复字符的子串	包含 t 所有字符的子串
”合法”定义	无重复字符	formed == required
while 条件	窗口不合法（有重复）	窗口合法（formed == required）
答案更新位置	while 循环之后	while 循环之内
目标	最大化 right - left + 1	最小化 right - left + 1
窗口状态	lastPos 或 freq[]	window[] + formed

这个对比表是理解可变窗口”双模式”的核心。收缩条件和答案更新位置正好相反，是最容易混淆的地方。

4.2 一个更深的视角：什么在驱动左指针移动

LeetCode 3（最长）：右指针扩展导致窗口不合法，左指针被迫移动（被”推”着走）。 LeetCode 76（最短）：窗口合法时，左指针主动收缩（主动去”探索”更短的合法窗口）。

用一个形象的比喻：

• 最长问题：左指针是个被动的”扫地僧”，只有当右指针带来麻烦时才出手清理
• 最短问题：左指针是个主动的”节约者”，每当条件满足时就迫不及待地往前走，争取找到更短的答案

这个视角帮助你在面试中快速判断：我的左指针应该是”被动清理型”还是”主动优化型”？

---

第 5 章 举一反三：LeetCode 76 的变体识别

5.1 LeetCode 727 最小窗口子序列（选做）

在”最小覆盖子串”的基础上，如果 t 中字符还需要保持相对顺序（即 t 是 s 的子序列而不是子集），问题就变成了 LeetCode 727。这道题需要双指针 + 回溯，超出本专栏范围，但了解这个变体有助于体会”覆盖”和”子序列”的区别。

5.2 LeetCode 438 找到字符串中所有字母异位词

与 76 类似，但目标是找所有固定长度的异位词（而不是最短的覆盖子串），属于固定窗口 + 字符计数，在第 06 篇详细讲解。

5.3 变形识别规律

当你看到以下组合时，几乎必然是最小覆盖子串的框架：

• “最短子串/最小子数组” + “包含/覆盖某些元素”
• “至少包含” + “连续区间”

而以下组合则是”最长无重复”的框架：

• “最长子串/子数组” + “不含重复/不超过 k 种字符”
• “至多包含 k 个不同字符”

设计哲学：模式识别先于代码

最小覆盖子串（困难）能被快速解出，不是因为背了代码模板，而是因为能快速识别”这是可变窗口的最短模式”。模式识别的训练，比重复练习同一道题有价值得多。

---

本篇总结

本篇深度解析了可变窗口的两道经典题：

1. LeetCode 3（最长无重复）：收缩条件是”窗口不合法”，答案在循环之后更新；lastPos 技巧让收缩可以直接跳，而非逐步移动
2. LeetCode 76（最小覆盖）：收缩条件是”窗口合法”（尝试找更短的合法窗口），答案在循环内部更新；need[]/window[]/formed 三件套是字符覆盖类问题的标准工具

可变窗口的两条黄金法则：

• 求最长 → while(不合法) 时收缩，收缩后更新答案
• 求最短 → while(合法) 时收缩，收缩前更新答案

下一篇讨论另一类可变窗口：最长”扩张型”窗口（LeetCode 424、1004），它的特点是”允许修改有限个元素”，收缩逻辑有一个非常反直觉的优化技巧——“不缩反扩”。

---

参考与延伸

• 01 滑动窗口算法原理全景：从暴力枚举到 O(n) 的思维跃迁 — 可变窗口的基础框架
• 02 固定长度滑动窗口：模板推导与三题精讲 — need/window 计数器的基础版本
• 06 字符计数窗口：哈希表与滑动窗口的黄金组合 — 字符计数类窗口的进阶

---

课后练习

LeetCode 340 - 至多包含 K 个不同字符的最长子串（中等，会员题）

在字符串 s 中，找至多包含 k 个不同字符的最长子串长度。

提示：可变窗口最长模板，用 Map<Character, Integer> 统计窗口内各字符频率；当 map.size() > k 时收缩，收缩时若某字符频率降为 0 则 map.remove(c)。这道题和 LeetCode 904（水果成篮）是同一类型，用本篇模板直接套用。