【Hot 100 刷题计划】 LeetCode 76. 最小覆盖子串 | C++ 滑动窗口题解

LeetCode 76. 最小覆盖子串 | C 滑动窗口高阶模板题解 题目描述题目级别困难 (Hard)给定两个字符串s和t长度分别是m和n。返回s中的最短窗口子串使得该子串包含t中的每一个字符包括重复字符。如果没有这样的子串返回空字符串。测试用例保证答案唯一。示例输入s ADOBECODEBANC,t ABC输出BANC解释最小覆盖子串BANC包含来自字符串t的A、B和C。 解题思路滑动窗口通用模板寻找满足某种条件的“最短子串”是滑动窗口的绝对主场。这道题的核心难点在于如何快速判断当前窗口内是否已经凑齐了t中的所有字符我们引入两个哈希表need和windows以及一个极其巧妙的变量validneed记录字符串t中每个字符需要的数量。windows记录当前滑动窗口中这些目标字符出现的数量。valid记录当前窗口中已经满足数量要求的字符种类数。当valid need.size()时说明窗口已经完全覆盖了t核心运作机制两步走战略步骤一向右扩张寻找可行解右指针r不断向右移动把新字符加入windows。如果加入的字符恰好是need中需要的并且数量刚好达标我们就让valid。目标一直向右扩张直到valid need.size()此时我们找到了一个“可行解”虽然可能很长。步骤二向左收缩优化最优解一旦窗口满足了条件valid need.size()我们就暂存当前的子串长度和起始位置并尝试逼近极限。左指针l开始向右移动把字符从窗口中“吐出来”。如果吐出的字符恰好是关键字符且导致窗口内该字符的数量低于了need的要求那valid--窗口不再合法。目标剥离边缘的无用字符找到满足条件的“最短”长度。窗口就在这样“扩张 - 满足条件 - 收缩 - 不满足条件 - 再次扩张”的博弈中不断刷新最短记录直到遍历完整个字符串。 C 代码实现classSolution{public:stringminWindow(string s,string t){// need 记录目标字符串 t 中每个字符的需求量// windows 记录当前窗口中对应字符的拥有量unordered_mapchar,intwindows,need;for(charc:t)need[c];intl0,r0;intvalid0;// 记录窗口中满足 need 条件的字符种类数// 记录最小覆盖子串的起始索引及长度intst0,lenINT_MAX;while(rs.size()){// c 是将移入窗口的字符同时右指针向右移动charcs[r];// 进行窗口内数据的一系列更新if(need.count(c)){windows[c];// 当该字符的数量刚好达到目标要求时满足条件的种类数 1if(windows[c]need[c]){valid;}}// 判断左侧窗口是否要收缩 (当所有的字符种类都达标时)while(validneed.size()){// 在这里更新最小覆盖子串的记录if(r-llen){stl;lenr-l;}// d 是将移出窗口的字符同时左指针向右移动chards[l];// 进行窗口内数据的一系列更新if(need.count(d)){// 如果移出的字符是关键字符且移出后数量不达标了种类数 -1if(windows[d]need[d]){valid--;}windows[d]--;}}}// 返回最小覆盖子串如果没有找到则返回空字符串returnlenINT_MAX?:s.substr(st,len);}};