16.滑动窗口经典例题：最小覆盖子串（LeetCode 76）算法原理剖析
目录
一、题目解析
二、讲解算法原理
解法一：暴力枚举 + 哈希表
解法二：滑动窗口 + 哈希表
优化：判断条件
三、代码实现
大家好，今天我们来攻克 LeetCode 上的一道经典难题——76. 最小覆盖子串。这道题是滑动窗口算法的典型应用，结合了哈希表来优化判断过程。
一、题目解析
题目： 给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。
注意：
对于
t中重复字符，我们寻找的子串中该字符数量必须不少于t中该字符数量。如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：
s = "ADOBECODEBANC",t = "ABC"输出：
"BANC"解释： 最小覆盖子串
"BANC"包含来自字符串t的'A'、'B'和'C'。
示例 2：
输入：
s = "a",t = "a"输出：
"a"解释： 整个字符串
s是最小覆盖子串。
示例 3：
输入：
s = "a",t = "aa"输出：
""解释：
t中两个字符'a'均应包含在s的子串中，因此没有符合条件的子子串，返回空字符串。
二、讲解算法原理
解法一：暴力枚举 + 哈希表
解法二：滑动窗口 + 哈希表
这是本题的最优解。核心思想是维护一个窗口[left, right]，通过移动左右指针来寻找最小覆盖子串。
核心逻辑：
right 右移： 不断扩大窗口，直到窗口包含了
t中的所有字符。left 右移： 在满足覆盖条件的前提下，尝试缩小窗口左边界，以找到最小长度。
优化：判断条件
为了优化每次判断窗口是否覆盖t的时间复杂度，我们可以引入一个变量count。
思路： 使用变量
count标记有效字符的种类。进窗口： 当
hash2[in] == hash1[in]时，count++。出窗口： 当
hash2[out] == hash1[out]时，count--。判断条件： 当
count == hash1.size()时，说明窗口已覆盖t。
三、代码实现
class Solution { public String minWindow(String ss, String tt) { char[] s = ss.toCharArray(); char[] t = tt.toCharArray(); int[] hash1 = new int[128]; // 统计字符串 t 中字符的频次 int kinds = 0; // 字符串 t 中，有多少种字符 for(char ch : t) { if(hash1[ch]++ == 0) kinds++; } int[] hash2 = new int[128]; // 统计窗口中字符的频次 int minlen = Integer.MAX_VALUE, begin = -1; for(int left = 0, right = 0, count = 0; right < s.length; right++) { char in = s[right]; if(++hash2[in] == hash1[in]) count++; // 进窗口 + 维护 count while(kinds == count) // 判断 { // 更新结果 if(right - left + 1 < minlen) { begin = left; minlen = right - left + 1; } char out = s[left++]; if(hash2[out]-- == hash1[out]) count--; // 出窗口 + 维护 count } } if(begin == -1) return new String(); else return ss.substring(begin, begin + minlen); } }