【LeetCode Hot100】最小覆盖子串[特殊字符]滑动窗口+哈希表，Java实现！图解+代码，小白也能秒懂！

💻 [LeetCode Hot100] 最小覆盖子串🔥滑动窗口+哈希表，Java实现！图解+代码，小白也能秒懂！

✏️本文对应题目链接：最小覆盖子串

📌 题目描述

给定一个字符串 s 和一个字符串 t，请在 s 中找出包含 t 所有字符的最小子串。

示例：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小子串 "BANC" 包含字符串 t 的所有字符 'A'、'B' 和 'C'。

🧠 解题思路（图文分解）

❗ 核心难点

如何在O(n)时间复杂度内找到包含 t 所有字符的最小子串？

方法一：滑动窗口 + 哈希表（黄金思路）✨

关键步骤：

1. 初始化：
   • 使用哈希表 need 记录 t 中每个字符的需求量
   • 使用哈希表 window 记录窗口中每个字符的数量
   • 定义滑动窗口的左右边界 left 和 right
2. 遍历字符串 s：
   • 扩展窗口：移动 right，更新 window 和匹配字符数 valid
   • 收缩窗口：当 valid 满足 t 的需求时，移动 left，更新最小子串
3. 返回结果：最小子串

图解滑动窗口

输入字符串：

s = "ADOBECODEBANC", t = "ABC"

步骤1：初始化

need = {'A':1, 'B':1, 'C':1}
window = {}
left = 0, right = 0
valid = 0
minLen = ∞, start = 0

步骤2：遍历字符串

right=0: 'A' → window={'A':1} → valid=1
right=1: 'D' → window={'A':1} → valid=1
right=2: 'O' → window={'A':1} → valid=1
right=3: 'B' → window={'A':1, 'B':1} → valid=2
right=4: 'E' → window={'A':1, 'B':1} → valid=2
right=5: 'C' → window={'A':1, 'B':1, 'C':1} → valid=3 → 更新最小子串 (len=6, start=0)
→ 满足条件，收缩窗口
left=0: 'A' → window={'B':1, 'C':1} → valid=2
right=6: 'O' → window={'B':1, 'C':1} → valid=2
right=7: 'D' → window={'B':1, 'C':1} → valid=2
right=8: 'E' → window={'B':1, 'C':1} → valid=2
right=9: 'B' → window={B':2, 'C':1} → valid=2
right=10: 'A' → window={'B':2, 'C':1, 'A':1} → valid=3→更新最小子串 (len=6, start=1)
→ 满足条件，收缩窗口
left=1: 'D' → window={'B':2, 'C':1, 'A':1} → valid=3 → 更新最小子串 (len=10, start=2)
left=2: 'O' → window={'B':2, 'C':1, 'A':1} → valid=3 → 更新最小子串 (len=9, start=3)
left=3: 'B' → window={'B':1, 'C':1, 'A':1} → valid=3 → 更新最小子串 (len=8, start=4)
left=4: 'E' → window={'B':1, 'C':1, 'A':1} → valid=3 → 更新最小子串 (len=7, start=5)
left=5: 'C' → window={'B':1, 'A':1} → valid=2 → 停止收缩
right=11: 'N' → window={'B':1, 'A':1} → valid=2
right=12: 'C' → window={'B':1, 'A':1, 'C':1} → valid=3 → 更新最小子串 (len=7, start=6)
→ 满足条件，收缩窗口
left=6: 'O' → window={'B':1, 'A':1, 'C':1} → valid=3 → 更新最小子串 (len=6, start=7)
left=7: 'D' → window={'B':1, 'A':1, 'C':1} → valid=3 → 更新最小子串 (len=5, start=8)
left=8: 'E' → window={'B':1, 'A':1, 'C':1} → valid=3 → 更新最小子串 (len=4, start=9)

最终结果：

最小子串 = "BANC"

🚀 代码实现

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

        // 初始化 need 和 window 哈希表
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0; // 滑动窗口的左右边界
        int valid = 0; // 记录窗口中满足 need 条件的字符个数
        int start = 0, minLen = Integer.MAX_VALUE; // 记录最小子串的起始位置和长度

        // 遍历字符串 s
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 更新窗口数据
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }

            // 当 valid 满足 need 的大小时，收缩窗口
            while (valid == need.size()) {
                // 更新最小子串
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }
                char d = s.charAt(left);
                left++;
                // 更新窗口数据
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        // 返回最小子串
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

💡 复杂度分析

• 时间复杂度：O(n) → 每个字符最多被访问两次（扩展和收缩窗口）
• 空间复杂度：O(m) → m 为字符集大小，哈希表存储字符

🌟 总结要点

✅ 滑动窗口核心思想：动态维护满足条件的最小窗口
✅ 哈希表作用：快速判断字符是否满足需求
✅ 适用场景：字符串匹配、子串问题