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

小龙报个人主页作者简介C研发嵌入式机器人AI等方向学习者❄️个人专栏《优选算法》✨永远相信美好的事情即将发生文章目录前言一、串联所有单词的子串1.1题目1.2 算法原理1.2.1 算法思路1.3 代码二、最小覆盖子串2.1 题目2.2 算法原理2.2.1 算法思路2.2.2 算法流程2.3 代码总结与每日励志前言滑动窗口是字符串高频考点哈希表则是窗口匹配的核心辅助工具。本文选取两道典型 LeetCode 例题展开讲解一道以单词为匹配单元一道以单个字符为匹配单元覆盖异位词、最小覆盖子串两类经典场景。文中拆解算法底层逻辑给出可直接提交的 C 代码统一梳理双指针扩张、收缩窗口的完整流程帮你吃透滑动窗口通用解题模板快速掌握字符串匹配类题目的通用思路。一、串联所有单词的子串1.1题目链接串联所有单词的子串1.2 算法原理核心思想:滑动窗口 哈希表1.2.1 算法思路如果我们把每一个单词看成一个一个字母问题就变成了找到「字符串中所有的字母异位词」。无非就是之前处理的对象是一个一个的字符我们这里处理的对象是一个一个的单词。1.3 代码classSolution{public:vectorintfindSubstring(strings,vectorstringwords){vectorintret;//存储结果unordered_mapstring,inth1;//统计words的for(autoa:words)h1[a];intmwords.size(),ns.size();intlenwords[0].size();for(inti0;ilen;i){intcount0;//统计有效unordered_mapstring,inth2;for(intli,ri;rlenn;rlen){stringins.substr(r,len);h2[in];if(h2[in]h1[in])count;if(r-l1len*m){stringouts.substr(l,len);if(h2[out]--h1[out])count--;llen;}if(countm)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_MAXi. 如果相等说明没有匹配返回空串ii. 如果不相等说明匹配返回s中从retleft位置往后len长度的字符串。2.3 代码classSolution{public:stringminWindow(string s,string t){inthash1[128]{0};//统计t的每个字符出现次数inthash2[128]{0};//统计s的每个字符出现次数intkind0;//t中hash1有效字符出现的种类for(autoa:t){if(hash1[a]0)kind;}intl0,r0,ns.size();intcount0;//统计s中有效字符的种类intret1e610,begin-1;while(rn){charins[r];if(hash2[in]hash1[in])//进窗口 有效字符种类count;while(countkind)//判断{if(retr-l1)//更新结果{retr-l1;beginl;}charouts[l];if(hash2[out]--hash1[out])count--;}r;}if(begin-1)return;elsereturns.substr(begin,ret);}};时间复杂度: ON总结与每日励志✨两道例题均采用滑动窗口搭配哈希表的核心框架仅匹配粒度存在差异最小覆盖子串以单个字符为单位遍历串联单词子串按单词长度分多轮遍历。二者都通过哈希表统计目标元素频次用有效计数简化窗口合法性判断避免重复遍历哈希表把时间复杂度压缩至线性。掌握这套模板可解决绝大多数连续子串匹配题日常刷题可复用双指针扩张收缩逻辑高效处理各类字符串窗口类算法场景。