《算法题讲解指南：优选算法-滑动窗口》--15.串联所有单词的子串，16.最小覆盖子串

🔥小叶-duck：个人主页

❄️个人专栏：《Data-Structure-Learning》

《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心

✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游

目录

15. 串联所有单词的子串

题目链接：

题目描述：

题目示例：

解法（滑动窗口+哈希表）：

算法思路：

C++算法代码：

算法总结及流程解析：

16. 最小覆盖子串

题目链接：

题目描述：

题目示例：

解法 (滑动窗口+哈希表)：

算法思路：

算法流程：

C++算法代码：

算法总结及流程解析：

结束语

15. 串联所有单词的子串

题目链接：

30. 串联所有单词的子串 - 力扣（LeetCode）

题目描述：

题目示例：

解法（滑动窗口+哈希表）：

算法思路：

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

有以下几点不同：

• 哈希表需要使用 hash<string,int>
• left 和 right 移动的步长是单词的长度(len)
• 滑动窗口执行的次数也是 len 次

C++算法代码：

class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { //解法：滑动窗口 + 哈希表(容器) vector<int> ret; unordered_map<string, int> hash1; //统计 words 中所有单词出现的频次 //string表示存放的数据是string类型，int表示数据存放的次数 for(auto e : words) { hash1[e]++; } int len = words[0].size(); //len为 words 中每个字符串的长度 int m = words.size(); //m为 words 的长度，目的是为了和 count 相比较 int left = 0; int right = 0; for(int i = 0; i < len; i++) { unordered_map<string, int> hash2;//存放s中的子串 //放到第一个for循环中目的是：每轮判断完成后hash2需要进行重置 //避免上一轮hash2中存放的数据对第二轮造成影响 int count = 0;//统计窗口中“有效字符串”的个数 left = i; //for(right = i; right <= (int)s.size() - len; right += len) //写成上面s.size() - len的形式一定要注意size()返回的类型是size_t //当size_t类型与int类型进行运算时，结果会类型转换出size_t类型 //如果此时s.size() - len为负数则会变成最大值，导致substr越界访问right //所以我们需要先将s.size()返回类型强转成int类型才能进行运算 for(right = i; right + len <= s.size(); right += len) { string str1 = s.substr(right, len); hash2[str1]++; //进窗口 if(hash2[str1] <= hash1[str1]) { count++; } if(right - left + 1 > len * m) //判断 { string str2 = s.substr(left, len); if(hash2[str2] <= hash1[str2]) { count--; } hash2[str2]--; //出窗口 left += len; } if(count == m) //更新结果 { ret.push_back(left); } } } return ret; } };

算法总结及流程解析：

16. 最小覆盖子串

题目链接：

76. 最小覆盖子串 - 力扣（LeetCode）

题目描述：

题目示例：

解法 (滑动窗口+哈希表)：

算法思路：

      研究对象是连续的区间，因此可以尝试使用滑动窗口的思想来解决。

      如何判断当前窗口的所有字符是符合要求的呢？

• 我们可以使用两个哈希表。其中一个将目标串的信息统计起来，另一个哈希表动态的维护窗口内字符串的信息。
• 当动态哈希表中包含目标串中所有字符，并且对应的个数都不小于目标串的哈希表中各个字符的个数，那么当前的窗口就是一种可行的方案。

算法流程：

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

  2. 实现一个接口函数，判断当前窗口是否满足要求：

    2.1 遍历两个哈希表中对应位置的元素

      2.1.1 如果 t 中某个字符的数量大于窗口中字符的数量，也就是 hash2 某个位置大于 hash1 。说明不匹配，返回 false。

      2.1.2 如果全部匹配，返回 true。

主函数中：

  1.先将 t 的信息放入 hash2 中；

  2.初始化一些变量：左右指针：left = 0，right = 0；目标子串的长度：len = INT_MAX；目标子串的起始位置：begin；(通过目标子串的起始位置和长度，我们就可以找到结果)

  3.当 right 小于字符串 s 的长度时，一直下列循环：

    3.1 将当前遍历到的元素扔进 hash1 中；

    3.2 检测当前窗口是否满足条件；

      3.2.1 如果满足条件：

                        判断当前窗口是否变小。如果变小：更新长度 len，以及字符串的起始位置 begin

                        判断完毕后，将左侧的元素滑出窗口，顺便更新到 hash1；

                        重复上述两个过程，直到窗口不满足条件；

    3.3 right++，遍历下一个元素；

  4. 判断 len 的长度是否等于 INT_MAX;

    4.1 如果相等，说明没有匹配，返回空串；

    4.2 如果不相等，说明匹配，返回 s 中从 retleft 位置往后 len 长度的字符串。

C++算法代码：

class Solution { public: string minWindow(string s, string t) { // //解法一：滑动窗口 + 哈希表(使用容器)，count 标记“有效字符”的个数 // unordered_map<char, int> hash1; // for(auto c : t) // { // hash1[c]++; // } // int count = 0; int left = 0; int right = 0; // int n = t.size(); int min_len = s.size() + 1; int begin = -1; // string ret; // unordered_map<char, int> hash2; // for(right = 0; right < s.size(); right++) // { // hash2[s[right]]++; //进窗口 // if(hash2[s[right]] <= hash1[s[right]]) // { // count++; // } // while(hash2[s[left]] > hash1[s[left]]) //判断 // { // hash2[s[left]]--; //出窗口 // left++; // } // if(count == n) // { // if(min_len > right - left + 1) //更新结果 // { // min_len = right - left + 1; // begin = left; // } // } // } // if(begin != -1) // { // ret = s.substr(begin, min_len); // } // return ret; //优化：数组模拟实现哈希表，count 标记“有效字符”的种类 int hash1[128] = { 0 }; //统计字符串 t 中每个字符出现的频次 int kinds = 0; //统计“有效字符”有多少种 for(auto c : t) { if(hash1[c]++ == 0) { kinds++; } } int left = 0; int right = 0; int count = 0; int min_len = s.size() + 1; int begin = -1; string ret; int hash2[128] = { 0 }; for(right = 0; right < s.size(); right++) { hash2[s[right]]++; //进窗口 if(hash2[s[right]] == hash1[s[right]]) { count++; } while(count == kinds)//判断 { if(min_len > right - left + 1) //更新结果 { min_len = right - left + 1; begin = left; } if(hash2[s[left]] == hash1[s[left]]) { count--; } hash2[s[left]]--; //出窗口 left++; } } if(begin != -1) { ret = s.substr(begin, min_len); } return ret; } };

算法总结及流程解析：

结束语

       到此，15.串联所有单词的子串，16.最小覆盖子串 这两道算法题就讲解完了。《串联所有单词的子串》采用滑动窗口 + 哈希表方法，将单词视为字符处理，通过控制窗口步长和频次统计实现高效匹配；《最小覆盖子串》通过双哈希表动态维护目标串和窗口字符频次，优化版使用128位数组提升效率。希望大家能有所收获！