Hot 100 --- 最小覆盖子串

本文概览：本文以LeetCode经典题目"最小覆盖子串"为例，从暴力解法入手，逐步优化到双指针滑动窗口解法，重点讲解如何通过 match 变量动态维护哈希表的匹配状态，避免每次遍历比较，将时间复杂度从 O(n²×m) 优化到 O(n)

一、题目

最小覆盖子串题目

二、题目分析

给定字符串 s 和 t，在 s 中找到包含 t 所有字符（包括重复字符）的最小窗口子串

目标：返回 s 中涵盖 t 所有字符的最小子串，如果不存在则返回空字符串

核心问题：如何高效地判断当前窗口是否包含了 t 的所有字符，并在包含时尽可能收缩窗口找到最小长度

思路概览

Java实现代码如下

public String minWindow(String s, String t) {
    if (s == null || t == null || s.length() < t.length()) {
        return "";
    }

    // 记录目标Map
    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }

    // 记录当前的Map
    Map<Character, Integer> current = new HashMap<>();

    int match = 0;
    int left = 0; // 实时窗口左边界
    int minLen = Integer.MAX_VALUE; // 最小子串长度
    int minStart = 0; // 最小子串的起始

    // 右指针移动寻找符合条件窗口
    for (int right = 0; right < s.length(); right++) {
        // 添加对应元素进入当前map
        char key = s.charAt(right);
        current.put(key, current.getOrDefault(key, 0) + 1);

        // 判断添加元素后，该元素是否已经符合条件，符合则match++
        if (need.containsKey(key) && need.get(key).equals(current.get(key))) {
            match++;
        }

        // 判断当前子串是否已经符合条件
        while (match == need.size()) {
            // 当前的子串长度
            int currentLen = right - left;
            // 更新最小子串长度
            if (currentLen < minLen) {
                minLen = currentLen;
                minStart = left;
            }

            // 寻找最优解
            // 缩短左指针
            char c = s.charAt(left);
            current.put(c, current.get(c) - 1);
            // 判断移除左元素后是否还符合要求
            if (need.containsKey(c) && current.get(c) < need.get(c))
                match--;
            left++;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen + 1);
}

思路简要说明

双指针滑动窗口：右指针扩展窗口寻找符合条件的子串，左指针收缩窗口寻找最小长度
两个哈希表：need 记录 t 中各字符需要的数量，current 记录当前窗口中各字符的数量
match 变量动态维护：用 match 记录当前窗口中有多少种字符已经满足 t 的要求，当 match == need.size() 时说明窗口已涵盖 t 的所有字符

三、思路详解

暴力解法入手

最自然的想法是：枚举所有可能的窗口长度，从 t.length() 开始，固定窗口大小遍历 s，检查每个窗口是否包含 t 的所有字符。如果当前长度的窗口没找到，就把窗口长度 +1 继续遍历，直到第一次找到为止

显然可以得出以下结论

时间复杂度：最坏 O(n² × m)，n 为 s 的长度，m 为 t 的长度。窗口长度从 m 到 n，每种长度都要遍历一遍 s，每次还要检查是否包含 t
核心瓶颈：固定窗口大小逐个尝试，做了大量无效计算。很多窗口明显不包含 t 却还是要检查
关键思考：能否不固定窗口大小，而是动态调整窗口，找到一个符合条件的就尝试收缩？

双指针滑动窗口（遍历比较哈希表）

思路分析

暴力解法的问题在于固定窗口大小，效率太低。我们换一种思路：用左右两个指针动态维护一个窗口，右指针向右扩展窗口直到涵盖 t，然后左指针向右收缩窗口寻找最小长度

具体做法：

右指针不断右移，将字符加入当前窗口的哈希表
每次加入后，遍历比较 need 和 current 两个哈希表，检查当前窗口是否已经涵盖了 t 的所有字符
如果涵盖了，记录当前窗口长度，然后左指针右移收缩窗口
收缩后再次遍历比较，如果仍然涵盖就继续收缩，直到不涵盖为止

public String minWindow(String s, String t) {
    if (s == null || t == null || s.length() < t.length()) {
        return "";
    }

    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }

    Map<Character, Integer> current = new HashMap<>();
    int left = 0;
    int minLen = Integer.MAX_VALUE;
    int minStart = 0;

    for (int right = 0; right < s.length(); right++) {
        char key = s.charAt(right);
        current.put(key, current.getOrDefault(key, 0) + 1);

        // 遍历比较两个哈希表，判断是否涵盖
        while (isCovered(need, current)) {
            if (right - left < minLen) {
                minLen = right - left;
                minStart = left;
            }
            char c = s.charAt(left);
            current.put(c, current.get(c) - 1);
            if (current.get(c) == 0) current.remove(c);
            left++;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen + 1);
}

// 每次都要遍历need的所有key进行比较
private boolean isCovered(Map<Character, Integer> need, Map<Character, Integer> current) {
    for (Map.Entry<Character, Integer> entry : need.entrySet()) {
        if (current.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
            return false;
        }
    }
    return true;
}

这个方案比暴力解法好很多，但仍然有一个问题：每次判断窗口是否涵盖 t，都要遍历 need 哈希表的所有 key 进行比较

时间复杂度：O(n × m)，n 为 s 的长度，m 为 t 中不同字符的种类数。每次窗口变化都可能触发一次 isCovered 遍历
核心瓶颈：isCovered 方法每次都要遍历 need 的所有 key，当 t 中字符种类多时，频繁的比较操作开销不小
关键思考：能否不遍历哈希表，就能知道当前窗口是否已经涵盖了 t？

双指针滑动窗口 + 动态维护哈希表

思路分析

遍历比较哈希表的问题在于：每次都要全量比较，但窗口每次只变化一个字符（右指针加入一个或左指针移出一个），我们其实只需要关注这个变化的字符对匹配状态的影响

具体做法是额外引入一个 match 变量，动态维护当前窗口的匹配状态：

match 记录当前窗口中有多少种字符已经恰好满足 t 的要求
当 match == need.size() 时，说明 t 中所有种类的字符都已满足，窗口涵盖了 t

match 的更新规则

右指针加入字符时：

当新字符 key 加入 current 后，检查 need 中是否包含 key，且 current.get(key) 是否等于 need.get(key)。如果等于，说明这个字符从"不满足"变为"恰好满足"，match++

注意：只在等于的时候 match++，大于的时候不加。因为 match 统计的是"恰好满足"的种类数，一个字符的数量超过需求不算新的种类

左指针移出字符时：

当字符 c 从 current 中减少后，检查 need 中是否包含 c，且 current.get(c) 是否小于 need.get(c)。如果小于，说明这个字符从"满足"变为"不满足"，match--

为什么这样就能替代遍历比较？

因为 match 记录的是"已满足的种类数"，而 need.size() 是"需要满足的总种类数"。只要 match == need.size()，就说明每种需要的字符都满足了，无需逐个遍历比较。而 match 的增减只与当前变化的那个字符有关，所以每次只需 O(1) 就能更新匹配状态

举例说明

以 s = "ADOBECODEBANC", t = "ABC" 为例

need = {A:1, B:1, C:1}，need.size() = 3

步骤	right	字符	current	match	操作	窗口
1	0	A	{A:1}	1 (A满足)	扩展	A
2	1	D	{A:1,D:1}	1	扩展	AD
3	2	O	{A:1,D:1,O:1}	1	扩展	ADO
4	3	B	{A:1,D:1,O:1,B:1}	2 (B满足)	扩展	ADOB
5	4	E	{A:1,D:1,O:1,B:1,E:1}	2	扩展	ADOBE
6	5	C	{A:1,D:1,O:1,B:1,E:1,C:1}	3 (C满足)	扩展	ADOBEC

match == 3 == need.size()，涵盖！开始收缩

收缩步骤	left	移出字符	current	match	窗口	最小长度
1	0	A	{A:0,...} → A<need[A]	2	DOBEC	记录6
-	-	-	-	-	不涵盖，停止收缩	-

右指针继续移动...

步骤	right	字符	current	match	操作	窗口
7	6	O	{...,O:2}	2	扩展	DOBECO
8	7	D	{...,D:2}	2	扩展	DOBECOD
9	8	E	{...,E:2}	2	扩展	DOBECODE
10	9	B	{...,B:2}	2	扩展	DOBECODEB
11	10	A	{A:1,...}	3 (A再次满足)	扩展	DOBECODEBA

match == 3，涵盖！开始收缩

收缩步骤	left	移出字符	current	match	窗口	最小长度
1	1	D	{D:1,...}	3	OBECODEBA	-
2	2	O	{O:1,...}	3	BECODEBA	-
3	3	B	{B:1,...}	3	ECODEBA	-
4	4	E	{E:1,...}	3	CODEBA	-
5	5	C	{C:0,...} → C<need[C]	2	ODEBA	记录5

右指针继续移动...

步骤	right	字符	current	match	操作	窗口
12	11	N	{...,N:1}	2	扩展	ODEBAN
13	12	C	{C:1,...}	3 (C再次满足)	扩展	ODEBANC

match == 3，涵盖！开始收缩，最终收缩到 BANC，长度 4

最终结果为 "BANC"

时间复杂度：O(n)，左右指针各遍历一次 s，哈希表操作 O(1)
空间复杂度：O(m)，m 为 t 和 s 中字符种类数之和