（12）LeetCode 76. 最小覆盖子串

LeetCode 76. 最小覆盖子串滑动窗口详解 题目描述给你两个字符串s和t长度分别为m和n。请你返回s中最短的子串使得该子串包含t中的所有字符包括重复字符。如果不存在这样的子串则返回空字符串。注意测试用例保证答案唯一。如果s中没有覆盖t的子串返回。示例 1输入s ADOBECODEBANC, t ABC 输出BANC 解释最短覆盖子串是 BANC长度为3虽然 ADOBEC 也包含 ABC但更长。示例 2输入s a, t a 输出a示例 3输入s a, t aa 输出 解释t 中两个 a 都需要被覆盖但 s 只有一个故返回 。 解题思路本题是经典的滑动窗口问题可以使用双指针哈希表在O ( m ) O(m)O(m)时间内解决。核心思想用哈希表ht记录目标字符串t中每个字符的出现次数即“需求量”。维护一个滑动窗口[j, i]其中i是右指针j是左指针。用另一个哈希表hs记录当前窗口内字符的实际出现次数。引入一个计数器cnt记录当前窗口中“有效匹配”的字符个数即窗口中已经满足t需求的字符数量。扩展右指针每次加入新字符若该字符在窗口中的数量不超过需求量则cnt。收缩左指针当窗口包含所有t的字符后即cnt t.size()尝试向右移动左指针去掉冗余字符以缩小窗口长度。在收缩过程中更新最小窗口。 代码实现CclassSolution{public:stringminWindow(string s,string t){unordered_mapchar,inths,ht;// hs: 窗口频次ht: 目标频次for(charc:t)ht[c];// 统计 t 中每个字符的需用量string res;// 最终答案intcnt0;// 窗口中有效匹配的字符个数for(inti0,j0;is.size();i){// 1. 扩展右边界将 s[i] 加入窗口hs[s[i]];if(hs[s[i]]ht[s[i]])cnt;// 若该字符的数量未超过需求量则有效计数1// 2. 收缩左边界移除窗口左侧所有冗余字符while(hs[s[j]]ht[s[j]]){hs[s[j]]--;// 移除左边界字符j;// 左指针右移}// 3. 如果窗口已经覆盖 t尝试更新答案if(cntt.size()){intcurLeni-j1;if(res.empty()||curLenres.size()){ress.substr(j,curLen);}}}returnres;}}; 代码逐行详解1️⃣ 哈希表初始化unordered_mapchar,inths,ht;for(charc:t)ht[c];ht存储了t中每个字符的需求次数例如t AAB则ht[A]2, ht[B]1。hs初始为空用于动态记录当前窗口[j, i]内字符出现的次数。2️⃣ 遍历右指针ifor(inti0,j0;is.size();i){hs[s[i]];if(hs[s[i]]ht[s[i]])cnt;...}每次将s[i]纳入窗口先更新hs。如果该字符在窗口中的数量没有超过它在t中的需求量说明这个字符是有效的cnt。例如t中需要 2 个A窗口已有 1 个A再来一个A时hs[A]2满足 ht[A]因此cnt。若再来第三个Ahs[A]3 2则不会增加cnt。3️⃣ 收缩左指针jwhile(hs[s[j]]ht[s[j]]){hs[s[j]]--;j;}当窗口已包含所需所有字符时cnt t.size()我们需要尽可能缩短窗口。检查左指针j指向的字符是否冗余即窗口中的数量超过了需求量。如果是则将其移出窗口频次减1左指针右移直到左边界字符不再冗余为止。此步骤保证了窗口在满足覆盖的前提下左边界无法再向右移动即当前窗口是以i为右边界时的最小窗口。4️⃣ 更新答案if(cntt.size()){if(res.empty()||i-j1res.size())ress.substr(j,i-j1);}当cnt t.size()时表示窗口已经覆盖了t的全部字符。此时比较当前窗口长度是否小于已记录的最短长度若是则更新res。 为什么cnt t.size()能保证覆盖cnt统计的是窗口中有效字符的总数每个有效字符意味着该字符在窗口中的出现次数没有超过它在t中的需求量。当cnt t.size()时说明窗口中已经累积了恰好等于t长度的有效字符且由于收缩步骤保证了任意字符均不超过需求量因此窗口内每个字符的数量正好等于或大于等于但冗余已被移除需求即完全覆盖t。 复杂度分析时间复杂度O ( m ) O(m)O(m)其中m mm是字符串s的长度。左右指针均只会向右移动每个字符最多被加入和移出窗口各一次因此总操作次数为O ( m ) O(m)O(m)。空间复杂度O ( ∣ Σ ∣ ) O(|\Sigma|)O(∣Σ∣)其中∣ Σ ∣ |\Sigma|∣Σ∣是字符集大小本题通常为 52 个英文字母或扩展为 256 个 ASCII 字符。哈希表存储的字符种类有限可视为O ( 1 ) O(1)O(1)。 测试用例验证输入输出解释s ADOBECODEBANC, t ABCBANC最短覆盖子串s a, t aa单字符匹配s a, t aa无法覆盖两个 ‘a’s aa, t aaaa必须完全匹配两个 ‘a’s bbaa, t ababaa注意顺序不影响子串包含即可 总结与扩展滑动窗口是解决子串/子数组问题的重要技巧常用于求满足条件的最短/最长区间。本题的核心难点在于如何高效判断窗口是否覆盖t以及如何处理重复字符。使用双哈希表 计数器是解决此类问题的经典范式掌握后可轻松应对 LeetCode 438、567 等相似题目。