【LeetCode76_滑动窗口】最小覆盖子串问题

引言

对于编程初学者来说，“最小覆盖子串”（LeetCode 76题）是理解滑动窗口思想的绝佳案例。这道题看似复杂，但只要拆解清楚每一步逻辑，就能从“看不懂”到“能手写”。本文会用最通俗的语言、最细致的步骤，结合完整代码和流程图，带你吃透这道经典题。

题目链接：【点击进入】

目录

一、先把题目说清楚

题目要求

给你两个字符串s和t，请在s中找出包含t所有字符的最短连续子串，如果s中不存在这样的子串，返回空字符串""。

关键注意点（新手容易踩坑）

1. 子串是s中连续的一段，不是随便挑几个字符凑一起；
2. t中的字符可能重复，比如t = "aa"，那么子串里必须至少有两个a；
3. 要找最短的那个子串，没有就返回空。

举个例子：

• 输入：s = "ADOBECODEBANC"，t = "ABC"
• 输出："BANC"（包含A、B、C，且是最短的）

二、为什么不用暴力解法？

新手可能会想：把s的所有子串列出来，挨个检查是否包含t的所有字符，再挑最短的。但这种方法有致命问题：

• s长度为m时，子串数量是m*(m+1)/2，时间复杂度是O(m²)；
• 如果m是 10^5，计算量会达到 10^10，直接超时。

而滑动窗口算法能把时间复杂度降到O(m + n)（n是t的长度），效率提升百倍，这也是这道题的核心解法。

三、滑动窗口核心思想

想象你手里有一个可伸缩的“窗口”（比如纸条圈），在s这个长字符串上从左到右滑：

1. 扩大窗口：先把窗口右边拉大，直到窗口里包含t的所有字符；
2. 缩小窗口：再把窗口左边收紧，在“窗口仍包含t所有字符”的前提下，缩到最短；
3. 滑动重复：继续往右滑窗口，重复“扩大-缩小”，直到滑到s末尾。

整个过程就像“找东西”：先圈出一个包含目标的范围，再把范围缩到最小，既不丢东西，又最省空间。

四、代码逐行拆解（新手友好版）

先贴完整代码（和题目一致），再拆成“小模块”讲解，每个模块只解决一个小问题：

classSolution{public:stringminWindow(string s,string t){// 模块1：统计t的字符信息inthash1[128]={0};// 存t中每个字符的出现次数（ASCII码对应索引）intkinds=0;// t中有多少种不同的字符（比如t=ABC，kinds=3）for(auto&ch:t){if(hash1[ch]++==0){// 第一次遇到这个字符时，kinds+1kinds++;}}// 模块2：初始化窗口相关变量inthash2[128]={0};// 存当前窗口中每个字符的出现次数intminlen=INT_MAX;// 记录最小窗口长度（初始值设为最大整数）intbegin=-1;// 记录最小窗口的起始位置（初始为-1表示没找到）// 模块3：滑动窗口核心循环（双指针left/right）for(intleft=0,right=0,count=0;right<s.size();right++){// 步骤1：扩大窗口——把right指向的字符加入窗口charin=s[right];hash2[in]++;// 窗口中该字符数量+1// 如果窗口中该字符数量刚好等于t中的数量，说明这个字符“达标”了if(hash2[in]==hash1[in]){count++;// 达标字符的种类数+1}// 步骤2：缩小窗口——当所有字符都达标时，尝试缩到最短while(count==kinds){// 步骤2.1：更新最小窗口信息intcurrent_len=right-left+1;// 当前窗口长度if(current_len<minlen){minlen=current_len;// 更新最小长度begin=left;// 更新最小窗口起始位置}// 步骤2.2：把left指向的字符移出窗口charout=s[left];left++;// left指针右移，窗口左边界缩小// 如果移出后，该字符数量低于t的要求，说明这个字符“不达标”了if(hash2[out]==hash1[out]){count--;// 达标字符的种类数-1}hash2[out]--;// 窗口中该字符数量-1}}// 模块4：返回结果if(begin==-1){// 没找到符合条件的窗口return"";}else{// 从begin开始，截取长度为minlen的子串returns.substr(begin,minlen);}}};

模块1：统计t的字符信息

新手提问：为什么用数组hash1，而不是列表/字典？
答：因为字符的ASCII码范围是0-127（比如’A’=65，‘B’=66），用长度为128的数组，索引直接对应字符的ASCII码，访问速度是O(1)，比字典（哈希表）更快，代码也更简单。

举个例子：如果t = "ABC"，遍历后：

• hash1['A'] = 1（'A’在t中出现1次）
• hash1['B'] = 1，hash1['C'] = 1
• kinds = 3（t中有3种不同字符）

模块2：初始化窗口变量

• hash2：和hash1对应，专门统计当前窗口里的字符数量；
• minlen：初始值设为INT_MAX（C++里的最大整数），这样第一次找到有效窗口时，肯定能更新；
• begin：初始为-1，用来标记最小窗口的起始位置，最后如果还是-1，说明没找到有效窗口。

模块3：滑动窗口核心循环

这里用了双指针：right（右指针，负责扩大窗口）、left（左指针，负责缩小窗口），还有一个关键变量count（记录“窗口中达标字符的种类数”）。

关键步骤拆解（用例子说话）

还是用s = "ADOBECODEBANC"，t = "ABC"举例：

1. 扩大窗口：right从0开始右移，依次加入’A’、‘D’、‘O’、‘B’、‘E’、‘C’。当加入’C’时，hash2['A']=1、hash2['B']=1、hash2['C']=1，count=3（等于kinds=3），此时窗口是ADOBEC（left=0，right=5）。
2. 缩小窗口：
   • 先算当前窗口长度5-0+1=6，minlen更新为6，begin=0；
   • 移出left=0的’A’，hash2['A']变成0，count减到2，退出缩小循环；
   • right继续右移，直到再次让count=3，重复缩小步骤。
3. 最终结果：当right移到13（字符’C’）时，窗口是BANC（left=9，right=12），长度4，这是最小的，所以begin=9，minlen=4。

模块4：返回结果（收尾）

• 如果begin=-1，说明全程没找到有效窗口，返回空；
• 否则用substr(begin, minlen)截取子串，就是答案。

五、新手常见问题解答

问题1：为什么count统计的是“达标字符的种类数”，而不是总字符数？

答：比如t="AAB"，kinds=2（A和B）。如果窗口里有2个A和1个B，count=2（A和B都达标），此时窗口有效；如果统计总字符数，会分不清“数量是否够”（比如1个A和1个B，总字符数是2，但A不达标）。

问题2：缩小窗口时，为什么先left++，再改hash2？

答：out = s[left]先记录要移出的字符，然后left++移动指针，最后hash2[out]--减少该字符的计数，逻辑上是“先标记要移出的字符→移动指针→更新计数”，顺序不能乱。

问题3：如果t里有重复字符，比如t="AA"，代码能处理吗？

答：能！比如t="AA"，hash1['A']=2，kinds=1。只有当窗口里hash2['A']=2时，count=1，才会进入缩小窗口步骤，保证窗口里至少有2个A。

六、新手练习建议

1. 手动走一遍例子：拿s="ADOBECODEBANC"，t="ABC"，把每个步骤的left、right、count、hash2的值写下来，理解窗口的变化；
2. 修改测试用例：比如t="AA"，s="AA"，s="ABAACBAA"，跑一遍代码，看结果是否正确；
3. 替换数据结构：把数组hash1/hash2换成unordered_map，改写代码，对比两种方式的区别；
4. 同类题拓展：做完这道题，再做“找到字符串中所有字母异位词”（LeetCode 438）、“无重复字符的最长子串”（LeetCode 3），巩固滑动窗口思想。

七、总结

滑动窗口解最小覆盖子串的核心就3点：

1. 统计目标：先算清楚t的字符种类和数量；
2. 双指针控窗口：right扩、left缩，一扩一缩找最短有效窗口；
3. count做标志：用count判断窗口是否有效，避免重复检查。

对于编程初学者来说，不用一开始追求“最优解”，先理解每一步的逻辑，手动模拟执行过程，再慢慢优化。滑动窗口是算法里的高频考点，掌握这道题，相当于掌握了一大类字符串问题的解法！