汀的知识碎片

09 最小覆盖子串：滑动窗口的最难挑战

16 min read

最小覆盖子串：滑动窗口的最难挑战

摘要

Minimum Window Substring 是 LeetCode 中公认最难的滑动窗口题之一，难点在于同时维护多字符频次、判断”满足覆盖条件”、以及处理 t 中有重复字符的情形。本文从最简单的字符种类约束出发，逐步建立完整的 formed 计数器模型，然后推广到 Find All Anagrams，最后挑战 Substring with Concatenation of All Words。

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

1.1 题目

LeetCode 76 - Minimum Window Substring（困难）

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

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

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

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

输入：s = "a", t = "aa"
输出：""
解释：t 中两个字符 'a' 均需包含在子串中，而字符串 s 中只有一个字符 'a'。

1.2 暴力解法分析

暴力枚举所有子串 ，检查是否包含 t 的所有字符（用频次比较）， 枚举 + 检查，总时间 ，无法通过。

1.3 核心难点：如何判断窗口”覆盖 t”？

覆盖 t 的定义：对 t 中每个字符 c，窗口内 c 的出现次数 ≥ t 中 c 的出现次数。

设 need[c] 是 t 中字符 c 的需求量，window[c] 是当前窗口中 c 的数量。

“窗口覆盖 t”等价于：对所有 c，window[c] >= need[c]。

如何高效判断？逐一检查所有字符 ，每次移动都做一次检查太慢。

解决方案：formed 计数器

formed：当前窗口中，“已满足频次要求”的字符种类数。 required：t 中不同字符的种类数（需要全部满足才算覆盖）。

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

维护规则：

  • 加入字符 c：window[c]++，若 window[c] == need[c]（恰好满足），formed++
  • 移除字符 c：若移除前 window[c] == need[c]（即将不满足），formed--，然后 window[c]--

每次移动 维护 formed，检查覆盖条件也是 （比较 formed == required）。

1.4 完整解法

public String minWindow(String s, String t) {
    if (s.length() < t.length()) return "";
 
    // 建立 need（t 中字符频次）和 required（t 中不同字符种类数）
    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);
    int required = need.size();
 
    // 滑动窗口状态
    Map<Character, Integer> window = new HashMap<>();
    int formed = 0;  // 已满足频次要求的字符种类数
 
    // 答案记录
    int minLen = Integer.MAX_VALUE;
    int ansLeft = 0, ansRight = 0;
 
    int left = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
 
        // 1. 加入右端
        window.put(c, window.getOrDefault(c, 0) + 1);
        if (need.containsKey(c) && window.get(c).equals(need.get(c))) {
            formed++;  // c 的频次刚好满足 need[c]
        }
 
        // 2. 收缩：当窗口覆盖 t 时，尝试收缩找最短
        while (formed == required) {
            // 更新答案
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                ansLeft = left;
                ansRight = right;
            }
 
            // 移除左端
            char d = s.charAt(left);
            left++;
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) {
                    formed--;  // d 的频次即将低于 need[d]
                }
            }
            window.put(d, window.get(d) - 1);
        }
    }
 
    return minLen == Integer.MAX_VALUE ? "" : s.substring(ansLeft, ansRight + 1);
}

时间复杂度：，其中 ，。right 和 left 各最多移动 步，每步操作 。

空间复杂度：，哈希表最多存 个字符。

1.5 t 中有重复字符时的正确处理

这是这道题最容易出错的地方。以 t = "aa" 为例，need['a'] = 2。

当窗口中 window['a'] = 1 时，不算满足（还差一个 a），formed 不应该增加。只有当 window['a'] = 2 时才满足，formed++。

代码中的判断：if (window.get(c).equals(need.get(c))) formed++;

用 .equals() 而不是 ==：Integer 对象在值 > 127 时不会被缓存，== 比较的是引用而不是值，会产生错误结果。必须用 .equals() 比较 Integer 对象。

生产避坑：Integer 的 == 陷阱

Java 中 Integer 类型的 -128 到 127 会被缓存，== 比较可能正确；超出这个范围时，== 比较对象引用而不是值，产生 false。在 HashMap 中操作 Integer 值时，必须用 .equals() 进行值比较。这是 Java 特有的陷阱，面试中非常容易犯错。

1.6 答案记录的细节

这道题求最短覆盖子串，答案记录在收缩阶段的内层 while 里：每次 formed == required，记录当前窗口长度。

注意：记录的是 [ansLeft, ansRight]（包含两端），最后用 s.substring(ansLeft, ansRight + 1) 提取（Java 的 substring 是左闭右开区间）。

第 2 章 LeetCode 438：找到字符串中所有字母异位词

2.1 题目

LeetCode 438 - Find All Anagrams in a String（中等）

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词：两个字符串包含相同字符，每个字符出现的次数也相同（即互为排列）。

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

输入: s = "abab", p = "ab"
输出: [0,1,2]

2.2 解法

这道题与上一篇的 Permutation in String（LeetCode 567）本质相同：找所有长度为 p.length() 的子串，其字符频次与 p 匹配。区别在于 567 只需要判断存在性，438 需要记录所有满足条件的起始下标。

使用 formed 计数器 + 定长滑动窗口：

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (s.length() < p.length()) return result;
 
    int[] need = new int[26];
    int[] window = new int[26];
    for (char c : p.toCharArray()) need[c - 'a']++;
 
    int k = p.length();
    int required = 0;
    for (int n : need) if (n > 0) required++;
 
    int formed = 0;
 
    // 初始化第一个窗口
    for (int i = 0; i < k; i++) {
        char c = s.charAt(i);
        window[c - 'a']++;
        if (need[c - 'a'] > 0 && window[c - 'a'] == need[c - 'a']) formed++;
    }
    if (formed == required) result.add(0);
 
    // 滑动窗口
    for (int right = k; right < s.length(); right++) {
        int left = right - k;  // 即将移出的左端字符下标
 
        // 加入右端
        char in = s.charAt(right);
        window[in - 'a']++;
        if (need[in - 'a'] > 0 && window[in - 'a'] == need[in - 'a']) formed++;
 
        // 移除左端
        char out = s.charAt(left);
        if (need[out - 'a'] > 0 && window[out - 'a'] == need[out - 'a']) formed--;
        window[out - 'a']--;
 
        if (formed == required) result.add(left + 1);  // 新窗口起始下标是 left+1
    }
    return result;
}

时间复杂度：，n = s.length()，m = p.length()。 空间复杂度：。

第 3 章 LeetCode 30：串联所有单词的子串

3.1 题目

LeetCode 30 - Substring with Concatenation of All Words（困难）

给定一个字符串 s 和一个字符串数组 words，words 中所有字符串长度相同。找出 s 中所有是 words 的串联子串的起始位置。不需要考虑 words 中元素的顺序。

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]

输入：s = "barfoofoobarhefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]

3.2 与字符级滑动窗口的区别

前面的题处理的是字符级窗口（以字符为单位滑动），这道题的窗口单位是单词。将 words 中每个单词看作一个”字符”，问题转化为：在 s 中找一个窗口，包含 words.length 个连续的固定长度单词，且这些单词的频次与 words 完全匹配。

3.3 解法：以单词为单位的滑动窗口

设每个单词长度为 wordLen，总单词数为 wordCount，目标窗口总长度为 totalLen = wordLen * wordCount。

由于单词是固定长度的，从 s 的不同起点开始，可以将 s 切分成若干单词序列。起点的偏移量有 wordLen 种（0 到 wordLen-1），每种偏移量独立处理。

public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> result = new ArrayList<>();
    if (s.isEmpty() || words.length == 0) return result;
 
    int wordLen = words[0].length();
    int wordCount = words.length;
    int totalLen = wordLen * wordCount;
    int n = s.length();
 
    // 建立 words 的频次 map
    Map<String, Integer> need = new HashMap<>();
    for (String w : words) need.put(w, need.getOrDefault(w, 0) + 1);
 
    // 对每个偏移量 offset（0 到 wordLen-1），独立做滑动窗口
    for (int offset = 0; offset < wordLen; offset++) {
        Map<String, Integer> window = new HashMap<>();
        int formed = 0;  // 窗口内已满足频次的单词种类数
        int required = need.size();
        int left = offset;  // 窗口左端（以 offset 为起点，步长 wordLen）
 
        // right 以 wordLen 为步长扫描
        for (int right = offset; right + wordLen <= n; right += wordLen) {
            String word = s.substring(right, right + wordLen);
 
            if (need.containsKey(word)) {
                window.put(word, window.getOrDefault(word, 0) + 1);
                if (window.get(word).equals(need.get(word))) formed++;
            }
 
            // 当窗口包含的单词数超过 wordCount，收缩左端
            while ((right - left) / wordLen + 1 > wordCount) {
                String leftWord = s.substring(left, left + wordLen);
                if (need.containsKey(leftWord)) {
                    if (window.get(leftWord).equals(need.get(leftWord))) formed--;
                    window.put(leftWord, window.get(leftWord) - 1);
                    if (window.get(leftWord) == 0) window.remove(leftWord);
                }
                left += wordLen;
            }
 
            // 检查当前窗口是否满足条件
            if (formed == required && (right - left) / wordLen + 1 == wordCount) {
                result.add(left);
            }
        }
    }
    return result;
}

时间复杂度：，其中 n 是 s 的长度，每个偏移量处理 个单词，提取子串 ，共 wordLen 个偏移量，总计 。

空间复杂度：，哈希表存 k 个单词，每个单词长度 wordLen。

3.4 这道题为什么要按偏移量分组？

如果从 s[0] 开始按 wordLen 切分，只能覆盖 s[0], s[wordLen], s[2*wordLen], ... 这些起点的组合。实际上，答案的起点可能是 s[1], s[2], ...（只要起点下标 % wordLen 等于 offset，都属于同一组）。

将 s 按 offset 分成 wordLen 组，每组独立做滑动窗口，就能覆盖所有可能的起点。

第 4 章 三道题的难度梯度对比

4.1 从 Minimum Window Substring 到 Concatenation of All Words

题目窗口单位频次维护难点
Minimum Window Substring（76）字符formed 计数器可变窗口+最短，重复字符处理
Find All Anagrams（438）字符formed 计数器定长窗口+记录所有位置
Concatenation of All Words（30）单词（固定长度）单词频次 Map按偏移量分组，单词级滑动

三道题都使用相同的 formed 计数器模式，区别在于窗口单位和收缩/记录逻辑。

4.2 最难题的关键设计决策

LeetCode 76 的几个关键设计决策及其原因：

1. 为什么用 formed 而不是每次调用 Arrays.equals？

t 中可能有多种字符，全量比较每次 ，虽然是常数但常数较大。formed 计数器实现 的条件检查，更优。

2. 为什么答案记录在 while 内层而不是 for 外层？

这是”最短满足条件”类型，在满足条件后尽量收缩（找更短的窗口），每次收缩前先记录当前窗口作为候选答案。

3. 为什么 need 用 HashMap 而不是 int[26]？

题目说明 s 和 t 由英文字母组成，但可以大小写混合（"ADOBECODEBANC" 中有大写字母）。使用 int[52] 或 int[128]（ASCII）也可以，但 HashMap 更通用，且代码意图更清晰。

第 5 章 面试中如何讲清楚最小覆盖子串

5.1 分步骤清晰表达

面试中讲解 Minimum Window Substring，推荐分四步：

第一步（确认框架）：“这是一道’最短满足条件的子串’问题，用可变滑动窗口：right 扩张，满足覆盖条件时收缩 left 找最短，记录答案。”

第二步（定义状态）：“need[c] 是 t 中字符 c 的需求量，window[c] 是当前窗口中 c 的数量，formed 是已满足频次的字符种类数，required 是 t 中总字符种类数。formed == required 时窗口覆盖 t。”

第三步（状态维护）：“加入字符 c：window[c]++，若 window[c] == need[c] 则 formed++。移除字符 d：若 window[d] == need[d] 则 formed--，再 window[d]--。”

第四步（分析重复字符）：“t 中有重复字符时，只有 window[c] == need[c]（恰好满足需求量）时才计入 formed，而不是 window[c] >= need[c]（超过了也不额外计数）。“

小结

本文攻克了滑动窗口中最难的三道题：

  • Minimum Window Substring（76）：formed 计数器 + 可变窗口最短，注意重复字符处理和 Integer.equals() 陷阱
  • Find All Anagrams（438）：定长窗口 + formed 计数器，收集所有满足条件的起始位置
  • Concatenation of All Words（30）：以单词为单位的滑动窗口，按偏移量分组处理

三道题共同展示了滑动窗口的终极形态：维护复杂状态（字符/单词频次），利用 formed 计数器 判断条件，扩张-收缩状态机找最短/全部满足条件的子串。

下一篇是专栏的收官之作——双指针算法综合通关，梳理所有模型的识别决策树，总结面试中的常见错误模式，并给出系统性的练习路径建议。