最小覆盖子串：滑动窗口的困难级应用与字符频次管理

适读人群：已掌握基础滑动窗口的 Java 开发者 | 阅读时长：约22分钟 | 难度：Hard

---

开篇故事

有一次我做代码审查，看到一段文本处理的代码，同事老陈写了个功能：在一段日志字符串里找最短的片段，使得这个片段包含所有指定的关键字字符。他的实现是暴力枚举，嵌套两层循环，外加一个内层 containsAll 检查，整体是 O(n²×m) 的复杂度，m 是关键字字符数。当日志文件稍微大一点，这段代码就开始吃内存、跑得很慢。

我当时就说："这是最小覆盖子串问题，有 O(n) 的解法。"老陈表示不信——他觉得这个问题直觉上就应该需要 O(n²)。

于是我花了二十分钟给他画图讲解：关键在于"窗口满足条件时，不需要从头重新检查，只需要从左端收缩"。老陈听完直接服了，说算法课本上真的有用啊。

LeetCode 76 是我见过的最能体现滑动窗口思想精髓的题目之一。它比 LeetCode 3（无重复字符最长子串）难在哪里？难在窗口的"合法性判断"更复杂：不只是"窗口内有没有重复"，而是"窗口是否覆盖了 t 中所有字符及其频次"。

管理字符频次，同时维护"已满足字符数"这个计数器，是这道题的核心技术点。

---

一、题目解析

LeetCode 76. 最小覆盖子串（Minimum Window Substring）

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

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

输入输出示例：

示例 1（基础情况）：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含了字符 'A', 'B', 'C'

示例 2（s == t）：

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

示例 3（无解）：

输入：s = "a", t = "aa"
输出：""
解释：t 中需要两个 'a'，但 s 中只有一个

边界情况 4（t 有重复字符）：

输入：s = "ADOBECODEBANC", t = "AABC"
输出："ADOBECODEBA"
解释：需要两个 'A'，最短覆盖子串长度更长

边界情况 5（t 比 s 长）：

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

考察的核心知识点：

• 滑动窗口（不定长）
• 字符频次管理（HashMap 或数组）
• "已满足字符数" 计数器的维护
• 最小窗口的记录方式（起始位置+长度）

---

二、解法一：暴力解法

思路分析

枚举 s 中所有子串，对每个子串检查是否覆盖 t 中所有字符（频次满足），记录满足条件的最短子串。

如何检查子串是否覆盖 t？统计子串中每个字符的频次，与 t 中字符频次比较，每个字符都满足就是合法覆盖。

两层循环枚举起点和终点，内层统计频次，总体 O(n²×m)，m 是字符种类数（字母表大小）。实际上统计频次可以优化成 O(|t|) 预处理 + O(子串长度) 验证，但还是 O(n²) 级别。

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";
        
        // 统计 t 中各字符需要的频次
        int[] need = new int[128];
        for (char c : t.toCharArray()) need[c]++;
        
        int minLen = Integer.MAX_VALUE;
        int minStart = 0;
        
        // 枚举子串起点
        for (int i = 0; i < s.length(); i++) {
            int[] window = new int[128];
            // 枚举子串终点
            for (int j = i; j < s.length(); j++) {
                window[s.charAt(j)]++;
                // 检查当前子串是否覆盖 t
                if (covers(window, need)) {
                    int len = j - i + 1;
                    if (len < minLen) {
                        minLen = len;
                        minStart = i;
                    }
                    break; // 找到了以 i 为起点的最短覆盖，break 内层
                }
            }
        }
        
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }
    
    // 检查 window 中每个字符的频次是否都 >= need 中的要求
    private boolean covers(int[] window, int[] need) {
        for (int i = 0; i < 128; i++) {
            if (window[i] < need[i]) return false;
        }
        return true;
    }
}

时间复杂度：O(n² × 128)，即 O(n²)，n 是 s 的长度。

空间复杂度：O(128) = O(1)，字母表固定大小。

缺陷： 在 LeetCode 上会 TLE（超时），当 s 长度为 10^5 时，n² = 10^10，完全不可用。

---

三、解法二：滑动窗口+频次数组

优化思路

暴力的问题：每次移动起点都重新统计频次。滑动窗口的思路：维护一个"活的"窗口，右边界扩展时增加字符频次，左边界收缩时减少字符频次，每次操作都是 O(1)。

但如何高效判断窗口是否合法（覆盖了 t）？不能每次都遍历所有字符比较，那还是 O(128) 的判断。

关键技巧：维护一个 formed 计数器，表示已经满足频次要求的字符种类数。当 formed == required（required 是 t 中不同字符的数量）时，窗口合法。

每当窗口中某字符 c 的频次恰好达到 t 中 c 的频次要求时，formed++；当频次降到要求以下时，formed--。这样合法性判断变成 O(1)。

class Solution {
    public String minWindow(String s, String t) {
        if (t.length() > s.length()) return "";
        
        // 统计 t 中各字符需要的频次
        int[] need = new int[128];
        for (char c : t.toCharArray()) need[c]++;
        
        // t 中不同字符的数量
        int required = 0;
        for (int freq : need) if (freq > 0) required++;
        
        int[] window = new int[128];
        int formed = 0;  // 当前窗口中已满足频次要求的字符种类数
        
        int left = 0;
        int minLen = Integer.MAX_VALUE;
        int minStart = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            window[c]++;
            
            // 如果字符 c 的频次恰好满足了需求，formed++
            if (need[c] > 0 && window[c] == need[c]) {
                formed++;
            }
            
            // 窗口合法时，尝试收缩左边界
            while (formed == required) {
                // 更新最小窗口
                int len = right - left + 1;
                if (len < minLen) {
                    minLen = len;
                    minStart = left;
                }
                
                // 收缩左边界
                char leftChar = s.charAt(left);
                window[leftChar]--;
                if (need[leftChar] > 0 && window[leftChar] < need[leftChar]) {
                    formed--;  // 左边字符的频次降到要求以下，不再满足
                }
                left++;
            }
        }
        
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }
}

时间复杂度：O(|s| + |t|)，每个字符最多进出窗口各一次。

空间复杂度：O(128) = O(1)。

---

四、解法三：滑动窗口+HashMap（工业级，支持 Unicode）

核心洞见

上面数组版本在 ASCII 场景下很好，但字符范围扩展到 Unicode 时需要 HashMap。同时，HashMap 版本的 need 只存 t 中出现的字符，不像数组版本那样需要遍历全部 128 个槽位统计 required，代码更清晰。

这个版本是工业代码里会写的标准实现，逻辑和数组版本一样，但用 HashMap 表达更通用。

算法流程

完整 Java 代码

import java.util.HashMap;
import java.util.Map;

class Solution {
    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);
        }
        
        // t 中有多少种不同的字符需要被满足
        int required = need.size();
        
        // 窗口中各字符的当前频次
        Map<Character, Integer> window = new HashMap<>();
        
        int formed = 0;  // 当前窗口中已满足需求的字符种类数
        int left = 0;
        int minLen = Integer.MAX_VALUE;
        int minStart = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            
            // 右边界扩展：更新窗口字符频次
            window.merge(c, 1, Integer::sum);
            
            // 判断字符 c 是否刚好满足了需求
            // 只关心 t 中出现的字符
            if (need.containsKey(c) && window.get(c).equals(need.get(c))) {
                formed++;
            }
            
            // 当窗口合法时，尝试收缩左边界寻找更小的合法窗口
            while (left <= right && formed == required) {
                // 记录当前合法窗口（如果比历史最小更小）
                int len = right - left + 1;
                if (len < minLen) {
                    minLen = len;
                    minStart = left;
                }
                
                // 左边界收缩：移出 left 位置的字符
                char leftChar = s.charAt(left);
                window.merge(leftChar, -1, Integer::sum);
                
                // 如果移出的字符是 t 中需要的，且频次降到了需求以下
                if (need.containsKey(leftChar) &&
                    window.get(leftChar) < need.get(leftChar)) {
                    formed--;
                }
                
                left++;
            }
        }
        
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }
}

复杂度分析

时间复杂度：O(|s| + |t|)

推导过程：统计 t 频次 O(|t|)。主循环中，right 从 0 走到 |s|-1，每次操作是 O(1) 的 HashMap 操作。内层 while 循环中，left 也是从 0 单调递增到 |s|-1，left 和 right 合计移动 2|s| 次。总体 O(|s| + |t|)。

空间复杂度：O(|t|)

HashMap need 最多存 |t| 个字符，window 同样最多存字符集大小个字符（但受 t 限制，实际上只有 need 中的字符在 formed 计数里有意义）。

我在 LeetCode 上提交，运行时间 5ms，击败 96.2% 的 Java 用户。

---

五、举一反三

同类型题目

LeetCode 3. 无重复字符的最长子串

特殊情况：t 是所有不同字符，窗口内每个字符频次不超过 1。

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

找 s 中所有长度为 |p| 的子串，使得该子串是 p 的字母异位词（字符频次完全相同）。这是"固定长度"的滑动窗口，每次窗口长度达到 |p| 时检查是否满足，然后移动左边界。

LeetCode 567. 字符串的排列

判断 s2 中是否有 s1 的排列。和 438 类似，固定窗口大小为 |s1|。

LeetCode 239. 滑动窗口最大值

固定窗口大小，求每个窗口的最大值。需要用单调队列，不是频次类问题，但同属"滑动窗口"范畴。

解题模板对比

不定长窗口（本题）： 窗口大小动态变化，由合法性决定收缩时机。

固定长度窗口（438、567）： 窗口大小固定为 k，right - left == k 时必须移动 left。

// 固定窗口模板
for (int right = 0; right < s.length(); right++) {
    // 扩展
    window.merge(s.charAt(right), 1, Integer::sum);
    
    if (right >= k - 1) {  // 窗口达到目标大小
        // 检查是否满足条件
        if (formed == required) result.add(left);
        
        // 收缩（固定移除最左元素）
        char leftChar = s.charAt(left);
        window.merge(leftChar, -1, Integer::sum);
        if (need.containsKey(leftChar) &&
            window.get(leftChar) < need.get(leftChar)) {
            formed--;
        }
        left++;
    }
}

面试中的变体和追问

1. 为什么内层 while 是 while (formed == required) 而不是 if？ 答：因为收缩一次之后窗口可能还是合法的（左边移出的字符不是限制因素），需要继续收缩直到窗口不再合法，才能找到以当前 right 为右边界的最小合法窗口。

2. formed 计数器的核心判断 window[c] == need[c] 为什么用等于而不是大于等于？ 答：formed 只在频次"刚好从不满足到满足"时加一，即 window[c] 从 need[c]-1 变为 need[c] 时。如果用 >=，每次 window[c] 增加都可能触发 formed++，导致重复计数。

---

六、踩坑实录

坑一：Integer 比较用 == 而不是 equals

现象： 代码逻辑看起来完全正确，但某些用例返回了错误结果。打断点发现 formed 没有在该加的时候加。

原因： 比较 Integer 对象时用了 window.get(c) == need.get(c)。Java 的 Integer 对象，对于 -128 到 127 范围内的值有缓存（整数池），== 比较会是 true；但超出这个范围时，== 比较的是对象引用，两个值相同的 Integer 对象 == 返回 false。当字符频次超过 127 时（理论上是可能的），就会出错。

解法： 永远用 .equals() 比较 Integer 对象，或者先 unbox 成 int：window.get(c).intValue() == need.get(c).intValue()，或者直接用 int 数组代替 HashMap。

// 错误
if (window.get(c) == need.get(c)) formed++;

// 正确
if (window.get(c).equals(need.get(c))) formed++;
// 或者
if ((int) window.get(c) == (int) need.get(c)) formed++;

坑二：收缩时忘记检查 need 是否包含该字符

现象： 某些情况下 formed 被错误地减少，导致错过合法窗口。

原因： 收缩左边界时，对所有字符都判断是否影响 formed，但 formed 只和 t 中出现的字符有关。如果左边移出的字符不在 t 中，不应该影响 formed。

// 错误：没有检查是否在 need 中
window.merge(leftChar, -1, Integer::sum);
if (window.get(leftChar) < need.getOrDefault(leftChar, 0)) {
    formed--;  // 当 leftChar 不在 need 中，need.getOrDefault 返回 0，
               // window.get(leftChar) 可能 >= 0，不会减 formed，看似没问题
               // 但如果 leftChar 在 need 中且 need.get = 0（这不应该存在）...
}

// 更清晰的写法
if (need.containsKey(leftChar) && 
    window.get(leftChar) < need.get(leftChar)) {
    formed--;
}

坑三：最小窗口记录的更新时机

现象： 返回的子串长度不是最小，或者返回了一个不包含 t 所有字符的子串。

原因： 最小窗口的更新放在了收缩之后，而不是收缩之前。收缩之后窗口可能已经不合法了，记录的是不合法窗口的信息。

解法： 在 while (formed == required) 的循环体里，先记录当前窗口（合法），再收缩左边界。顺序必须是：记录 → 收缩 → 更新 formed → left++。

---

七、总结

LeetCode 76 是滑动窗口的集大成者。它比入门题难在需要维护更复杂的窗口状态，但核心逻辑和所有滑动窗口题目一样：right 扩展，left 在合法时收缩，找最优解。

三条核心要点：

1. formed 计数器是这道题的关键优化：它把 O(|字母表|) 的合法性检查降到了 O(1)。维护 formed 的逻辑是：频次"恰好达到"需求时加一，"恰好低于"需求时减一。

2. 整数比较要用 .equals() 或者先拆箱，这是 Java 基础知识，但在滑动窗口里很容易因为专注算法逻辑而忘记。

3. 最小窗口记录的位置在 while 循环体的开头（先记录再收缩），不能在收缩之后记录。

延伸思考：

这道题的思路可以推广到"流式数据中的最小覆盖窗口"：数据不断到来，需要实时维护满足条件的最小历史片段。工程上有很多类似的场景，比如监控告警中找最短时间窗口使得所有指标都异常过。理解了这道题，这类工程问题也就有了解题框架。