【LeetCode HOT100 】：最小覆盖子串——滑动窗口的经典应用题解

题目概述

题目名称：76. 最小覆盖子串
难度：困难
题目链接：https://leetcode.cn/problems/minimum-window-substring/

题目描述：
给定两个字符串s和t，返回s中涵盖t所有字符的最小子串。如果不存在，则返回空字符串""。

关键点：

• 涵盖意味着s子串中每个字符的数量必须不少于t中该字符的数量

• 答案唯一且连续子串

• 时间复杂度要求较高（数据规模可达 10^5）

示例：

text

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

解题思路总览

本题属于滑动窗口的经典应用。核心思路是维护一个动态窗口，通过移动右指针扩展窗口直至覆盖t中所有字符，再移动左指针收缩窗口以寻找最短覆盖子串。

解法一：滑动窗口 + 哈希表（通用解法）

核心思想

使用两个哈希表：

• need：记录字符串t中每个字符的需求数量

• window：记录当前窗口中每个字符的出现次数

维护一个valid变量，表示当前窗口中已满足需求量的字符种类数。当valid == need.size()时，说明当前窗口已覆盖t，此时尝试收缩左边界。

算法步骤

1. 初始化left = 0，valid = 0，最小长度minLen = ∞

2. 右指针right遍历s：

   • 将s[right]加入窗口

   • 如果该字符是需要的，且窗口内数量达到需求，valid++

   • 当valid == need.size()时：

     • 更新最短子串的起始位置和长度

     • 尝试移动左指针收缩窗口：

       • 左移前，如果左边界字符是需要的且窗口内数量刚好等于需求，valid--

       • 左边界字符移出窗口，left++

3. 返回最短子串

代码实现（Python）

python

class Solution: def minWindow(self, s: str, t: str) -> str: from collections import defaultdict need = defaultdict(int) for c in t: need[c] += 1 window = defaultdict(int) left = 0 valid = 0 start = 0 min_len = float('inf') for right in range(len(s)): c = s[right] if c in need: window[c] += 1 if window[c] == need[c]: valid += 1 while valid == len(need): if right - left + 1 < min_len: min_len = right - left + 1 start = left d = s[left] left += 1 if d in need: if window[d] == need[d]: valid -= 1 window[d] -= 1 return s[start:start + min_len] if min_len != float('inf') else ""

代码实现（Java）

java

class Solution { public String minWindow(String s, String t) { 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, valid = 0; int start = 0, minLen = Integer.MAX_VALUE; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) + 1); if (window.get(c).equals(need.get(c))) { valid++; } } while (valid == need.size()) { if (right - left + 1 < minLen) { minLen = right - left + 1; start = 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); } }

解法二：滑动窗口 + 数组（ASCII优化版）

核心思想

由于题目中的字符由英文字母组成，可以使用长度为 128 的数组代替哈希表，效率更高。数组下标直接对应字符的 ASCII 码。

代码实现（Python）

python

class Solution: def minWindow(self, s: str, t: str) -> str: need = [0] * 128 for c in t: need[ord(c)] += 1 window = [0] * 128 left = 0 count = 0 # 已满足需求的字符总数（非种类） min_len = float('inf') start = 0 for right in range(len(s)): idx = ord(s[right]) window[idx] += 1 if window[idx] <= need[idx]: count += 1 while count == len(t): if right - left + 1 < min_len: min_len = right - left + 1 start = left left_idx = ord(s[left]) if window[left_idx] <= need[left_idx]: count -= 1 window[left_idx] -= 1 left += 1 return s[start:start + min_len] if min_len != float('inf') else ""

注意：此版本使用count统计已满足需求的字符总数而非种类数，逻辑略有不同但效果相同。

解法三：优化滑动窗口（预处理有效字符）

核心思想

当字符串s很长但t很短时，s中大部分字符可能都不在t中。可以预先过滤掉这些无效字符，只保留s中出现在t里的字符及其下标，然后在过滤后的序列上应用滑动窗口。

适用场景

• s长度很大（如 10^5）

• t长度很小

• s中属于t的字符占比很低

算法步骤

1. 遍历s，记录所有属于t的字符及其在s中的下标

2. 在过滤后的字符序列上执行滑动窗口

3. 根据下标还原原字符串中的子串位置

代码实现（Python）

python

class Solution: def minWindow(self, s: str, t: str) -> str: from collections import defaultdict, Counter need = Counter(t) filtered = [(i, ch) for i, ch in enumerate(s) if ch in need] left = 0 window = defaultdict(int) valid = 0 start = 0 min_len = float('inf') for right in range(len(filtered)): idx, ch = filtered[right] window[ch] += 1 if window[ch] == need[ch]: valid += 1 while valid == len(need) and left <= right: left_idx, left_ch = filtered[left] curr_len = idx - left_idx + 1 if curr_len < min_len: min_len = curr_len start = left_idx if window[left_ch] == need[left_ch]: valid -= 1 window[left_ch] -= 1 left += 1 return s[start:start + min_len] if min_len != float('inf') else ""

复杂度分析对比

注：n = len(s)，m = len(t)

易错点总结

1. valid的含义：代表已满足数量要求的字符种类数，而非字符总数。当某字符的窗口计数恰好等于需求计数时才增加valid。

2. 窗口收缩条件：必须使用while而非if，因为收缩后窗口可能仍然满足覆盖条件，需要持续收缩。

3. 边界处理：当min_len仍为无穷大时，返回空字符串。

4. 字符重复处理：t中可能包含重复字符（如"aa"），需要确保窗口中有至少两个'a'。

相关题目推荐

参考链接

• 题目链接：LeetCode 76. 最小覆盖子串

• 官方题解

如果这篇文章对你有帮助，欢迎点赞、收藏、关注！🎉