力扣（最小覆盖子串）

剖析 LeetCode 76. 最小覆盖子串：哈希表与滑动窗口的完美协作

一、题目分析

（一）问题定义

给定字符串 s 和 t，找出 s 中包含 t 所有字符（字符数量需匹配，t 中重复字符需满足数量要求 ）的最小子串，返回该子串；若不存在，返回空字符串。例如 s = "ADOBECODEBANC"，t = "ABC"，最小覆盖子串为 "BANC" 。

（二）核心挑战

1. 字符匹配：需确保子串包含 t 的所有字符，且数量一致，这需要高效的字符计数方式。
2. 窗口伸缩：在 s 中动态调整滑动窗口的左右边界，找到包含 t 所有字符的最小窗口，避免暴力枚举所有子串（时间复杂度过高 ）。
3. 边界处理：准确判断窗口何时包含 t 的所有字符，以及如何收缩左边界以找到最小窗口。

二、算法思想：哈希表 + 滑动窗口协同

（一）哈希表的作用

• 字符计数：用哈希表 tMap 统计 t 中各字符的出现次数，作为匹配的“标准”；用 sMap 统计滑动窗口内 s 的字符出现次数，用于与 tMap 对比。
• 匹配判断：通过比较 sMap 和 tMap 中字符的计数，判断当前窗口是否包含 t 的所有字符（当 sMap 中各字符计数≥tMap 对应计数，且覆盖 tMap 所有键时，认为匹配 ）。

（二）滑动窗口的设计

• 右边界扩张：遍历 s 时，右边界 right 不断右移，将字符加入 sMap，并检查是否满足匹配条件。
• 左边界收缩：当窗口满足匹配条件时，尝试收缩左边界 left，缩小窗口范围，同时更新最小窗口的起始位置和长度，确保找到“最小”子串。

三、代码实现与详细注释

//哈希表+滑动窗口
class Solution {public String minWindow(String s, String t) {//建立两个哈希表//哈希表1：（存储字符串t的字符对应的值是字符的个数）//哈希表2：（存储字符串s的字符，以双指针指向的位置为头和尾，值为字符的个数）//哈希表1和哈希表2对比，相同就得到子串的开始和结束并与现在的长度进行比对//判断s是否小于t的长度，如果s大于t的长度则不可能存在覆盖字串,s和t为空也没有子串if (s.length() < t.length() || s == null || t == null) {return "";}//建立哈希表1Map<Character, Integer> tMap = new HashMap<>();//建立哈希表2Map<Character, Integer> sMap = new HashMap<>();for (int i = 0; i < t.length(); i++) {tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);}//建立，遍历s字符串int left = 0;int right = 0;Integer count = 0;int minLen = Integer.MAX_VALUE;int start = 0;while (right < s.length()) {char rightChar = s.charAt(right);//移动右边界并寻找最小覆盖子串if (tMap.containsKey(rightChar)) {sMap.put(rightChar, sMap.getOrDefault(rightChar, 0) + 1);if (tMap.get(rightChar).equals(sMap.get(rightChar))) {count++;}}//相同时证明找到了子串while (count.equals(tMap.size())) {//更新最小覆盖子串if (minLen - start > right - left) {minLen = right;start = left;}char leftChar = s.charAt(left);if (tMap.containsKey(leftChar)) {// 如果移除前数量刚好等于t中的数量，需要减少countif (sMap.get(leftChar).equals(tMap.get(leftChar))) {count--;}sMap.put(leftChar, sMap.get(leftChar) - 1);}//移动左边界left++;}right++;}return minLen==Integer.MAX_VALUE?"":s.substring(start,minLen+1);}
}

（一）代码流程拆解

1. 边界处理：若 s 长度小于 t 或任意字符串为空，直接返回空字符串，避免无效计算。
2. 初始化哈希表：tMap 统计 t 的字符计数；sMap 用于统计滑动窗口内 s 的字符计数。
3. 滑动窗口遍历：
   • 右边界扩张：right 遍历 s，将字符加入 sMap，并更新 count（记录满足 tMap 计数的字符种类数 ）。
   • 左边界收缩：当 count 等于 tMap 大小（窗口包含 t 所有字符 ），尝试收缩 left，更新最小窗口的起始位置和长度；同时处理 sMap 和 count，确保收缩后状态正确。
4. 结果返回：根据 minLen 是否更新，判断是否存在覆盖子串，返回对应结果。

（二）关键逻辑解析

• 字符匹配判断：通过 count 统计满足 tMap 计数的字符种类，避免逐个字符对比 sMap 和 tMap，提升效率。
• 窗口伸缩时机：右边界扩张寻找包含 t 的窗口，左边界收缩优化窗口大小，确保找到最小窗口。
• 计数更新细节：收缩左边界时，若移除的字符是 t 中的字符且计数刚好匹配 tMap，需减少 count，保证后续匹配判断准确。

四、复杂度分析

（一）时间复杂度

• 哈希表操作：遍历 t 初始化 tMap（O(m)，m 是 t 长度 ）；滑动窗口遍历 s（O(n)，n 是 s 长度 ），哈希表的 put、get 操作均为 O(1) 。
• 整体复杂度：O(m + n) ，线性时间复杂度，高效处理字符串匹配。

（二）空间复杂度

• 哈希表存储：tMap 存储 t 的字符（最多 m 个不同字符 ），sMap 存储滑动窗口内的字符（最多 n 个 ），空间复杂度 O(m + n) 。实际中，字符集有限（如英文字母 ），可视为 O(1) 。

LeetCode 76. 最小覆盖子串问题，通过哈希表 + 滑动窗口的协同策略，高效解决了字符匹配与最小窗口查找的难题。哈希表实现字符计数与快速匹配，滑动窗口动态调整边界，在一次遍历中完成匹配与优化。。