【优选算法】滑动窗口专项：1.串联所有单词的子串 2.最小覆盖子串

🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人，AI等方向学习者
❄️个人专栏：《优选算法》
✨永远相信美好的事情即将发生

前言

滑动窗口是字符串高频考点，哈希表则是窗口匹配的核心辅助工具。本文选取两道典型 LeetCode 例题展开讲解，一道以单词为匹配单元，一道以单个字符为匹配单元，覆盖异位词、最小覆盖子串两类经典场景。文中拆解算法底层逻辑，给出可直接提交的 C++ 代码，统一梳理双指针扩张、收缩窗口的完整流程，帮你吃透滑动窗口通用解题模板，快速掌握字符串匹配类题目的通用思路。

一、串联所有单词的子串

1.1题目

链接：串联所有单词的子串

1.2 算法原理

核心思想:滑动窗口 + 哈希表

1.2.1 算法思路

如果我们把每一个单词看成一个一个字母，问题就变成了找到「字符串中所有的字母异位词」。无非就是之前处理的对象是一个一个的字符，我们这里处理的对象是一个一个的单词。

1.3 代码

classSolution{public:vector<int>findSubstring(strings,vector<string>&words){vector<int>ret;//存储结果unordered_map<string,int>h1;//统计words的for(auto&a:words)h1[a]++;intm=words.size(),n=s.size();intlen=words[0].size();for(inti=0;i<len;i++){intcount=0;//统计有效unordered_map<string,int>h2;for(intl=i,r=i;r+len<=n;r+=len){stringin=s.substr(r,len);h2[in]++;if(h2[in]<=h1[in])count++;if(r-l+1>len*m){stringout=s.substr(l,len);if(h2[out]--<=h1[out])count--;l+=len;}if(count==m)ret.push_back(l);}}returnret;}};

时间复杂度: O(n)

二、最小覆盖子串

2.1 题目

链接：最小覆盖子串

2.2 算法原理

核心思想：滑动窗口 + 哈希表

• 研究对象是连续的区间，因此可以尝试使用滑动窗口的思想来解决。
• 如何判断当前窗口内的所有字符是符合要求的呢？

我们可以使用两个哈希表，其中一个将目标串的信息统计起来，另一个哈希表动态的维护窗口内字符串的信息。

当动态哈希表中包含目标串中所有的字符，并且对应的个数都不小于目标串的哈希表中各个字符的个数，那么当前的窗口就是一种可行的方案。

因为数据范围有限，可以使用数组来模拟哈希表

2.2.1 算法思路

a. 定义两个全局的哈希表：1 号哈希表hash1用来记录子串的信息，2 号哈希表hash2用来记录目标串 t 的信息；

b. 实现一个接口函数，判断当前窗口是否满足要求：
i. 遍历两个哈希表中对应位置的元素：
- 如果 t 中某个字符的数量大于窗口中字符的数量，也就是 2 号哈希表某个位置大于 1 号哈希表。说明不匹配，返回false；
- 如果全都匹配，返回true。

2.2.2 算法流程

主函数中：

a. 先将t的信息放入 2 号哈希表中；
b. 初始化一些变量：左右指针：left = 0, right = 0；目标子串的长度：len = INT_MAX；目标子串的起始位置：retleft；（通过目标子串的起始位置和长度，我们就能找到结果）
c. 当right小于字符串s的长度时，一直下列循环：
i. 将当前遍历到的元素扔进 1 号哈希表中；
ii. 检测当前窗口是否满足条件：
如果满足条件：
判断当前窗口是否变小。如果变小：更新长度len，以及字符串的起始位置retleft；
-判断完毕后，将左侧元素滑出窗口，顺便更新 1 号哈希表；
重复上面两个过程，直到窗口不满足条件；
iii.right++，遍历下一个元素；
d. 判断len的长度是否等于INT_MAX：
i. 如果相等，说明没有匹配，返回空串；
ii. 如果不相等，说明匹配，返回s中从retleft位置往后len长度的字符串。

2.3 代码

classSolution{public:stringminWindow(string s,string t){inthash1[128]={0};//统计t的每个字符出现次数inthash2[128]={0};//统计s的每个字符出现次数intkind=0;//t中hash1有效字符出现的种类for(autoa:t){if(hash1[a]++==0)kind++;}intl=0,r=0,n=s.size();intcount=0;//统计s中有效字符的种类intret=1e6+10,begin=-1;while(r<n){charin=s[r];if(++hash2[in]==hash1[in])//进窗口 + 有效字符种类count++;while(count==kind)//判断{if(ret>r-l+1)//更新结果{ret=r-l+1;begin=l;}charout=s[l++];if(hash2[out]--==hash1[out])count--;}r++;}if(begin==-1)return"";elsereturns.substr(begin,ret);}};

时间复杂度: O（N）

总结与每日励志

✨两道例题均采用滑动窗口搭配哈希表的核心框架，仅匹配粒度存在差异：最小覆盖子串以单个字符为单位遍历，串联单词子串按单词长度分多轮遍历。二者都通过哈希表统计目标元素频次，用有效计数简化窗口合法性判断，避免重复遍历哈希表，把时间复杂度压缩至线性。掌握这套模板可解决绝大多数连续子串匹配题，日常刷题可复用双指针扩张收缩逻辑，高效处理各类字符串窗口类算法场景。