算法每日双题精讲 —— 滑动窗口（串联所有单词的子串，最小覆盖子串）

🌟快来参与讨论💬，点赞👍、收藏⭐、分享📤，共创活力社区。 🌟

别再犹豫了！快来订阅我们的算法每日双题精讲专栏，一起踏上算法学习的精彩之旅吧！💪

今天，让我们一同来深入探讨 “串联所有单词的子串” 和 “最小覆盖子串” 这两道颇具挑战性的题目，看看滑动窗口算法在其中是如何施展其强大魔力的🧙‍♂️。

💯串联所有单词的子串

📖题目描述

🧠讲解算法原理

💻代码实现（以 C++ 为例）

💯最小覆盖子串

📖题目描述

🧠讲解算法原理

💻代码实现（以 C++ 为例）

💯串联所有单词的子串

题目链接👉【力扣】

📖题目描述

🧠讲解算法原理

暴力解法思路：
- 我们可以尝试遍历 s 中所有可能的子串，然后检查每个子串是否可以由 words 中的单词串联而成。对于长度为 m 的 s 和长度为 k 的 words 数组（每个单词长度为 n），总共有 $m-k*n+1$ 个可能的子串。对于每个子串，我们需要将其分割成 k 个长度为 n 的子单词，并与 words 中的单词进行比较，时间复杂度高，这种方法在实际中效率极低，几乎不可行。
滑动窗口解法思路：
- 我们可以利用滑动窗口来优化这个过程。首先，计算 words 中所有单词的总长度 totalLen = k * n。
- 然后，我们使用一个哈希表 wordCount 来记录 words 中每个单词的出现次数。
- 接着，我们在 s 上滑动窗口，窗口大小为 totalLen。每次滑动窗口时，我们将窗口内的子串分割成 k 个长度为 n 的子单词，并使用另一个哈希表 windowCount 来记录窗口内每个单词的出现次数。
- 如果 windowCount 和 wordCount 完全相同，那么当前窗口就是一个符合要求的子串，记录其起始位置。
- 为了避免重复计算，我们可以在窗口滑动时，只更新窗口左侧移除单词和右侧新加入单词的计数，而不是每次都重新计算整个窗口内的单词计数。
- 进一步优化思路：我们可以注意到，由于 words 中的单词长度相同，我们可以每次移动窗口时，不是逐个字符移动，而是以单词长度为单位移动。这样可以减少不必要的计算，进一步提高算法效率。

💻代码实现（以 C++ 为例）

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {//创建hash1记录words//创建hash2记录窗口里面//更新结果//要遍历len次vector<int> result;int len=words[0].size(),m=words.size();unordered_map<string,int> hash1;for(auto word:words){hash1[word]++;}for(int i=0;i<len;i++)//执行len次窗口{unordered_map<string,int> hash2;for(int left=i,right=i,count=0;right+len<=s.size();right+=len)//count是有效字符串的个数{//进窗口string in =s.substr(right,len);hash2[in]++;if(hash2[in]<=hash1[in]) count++;if(right-left+1>len*m)//出窗口{string out=s.substr(left,len);if(hash2[out]<=hash1[out]) count--;hash2[out]--;left+=len;}if(count==m) result.push_back(left);}}return result;}
};

💯最小覆盖子串

题目链接👉【力扣】

📖题目描述

🧠讲解算法原理

滑动窗口解法思路：
- 首先，我们使用一个哈希表 targetCount 来记录字符串 t 中每个字符的出现次数。
- 然后，我们在 s 上使用滑动窗口。窗口的左右边界分别为 left 和 right，初始时都为 0。
- 当 right 向右移动时，我们将新进入窗口的字符在另一个哈希表 windowCount 中的计数加 1，并检查该字符的计数是否等于在 targetCount 中的计数。如果相等，说明我们找到了一个在 t 中出现的字符，我们可以增加一个计数器 valid，表示当前窗口中已经包含了多少个 t 中的不同字符。
- 当 valid 等于 t 中不同字符的数量时，说明当前窗口可能是一个覆盖子串。此时，我们尝试将 left 向右移动，缩小窗口，同时更新 windowCount 和 valid。在移动 left 的过程中，我们要确保窗口仍然覆盖 t 中的所有字符。当窗口不能再缩小时，此时的窗口就是以 right 为右端点的最小覆盖子串，我们记录其长度和起始位置。
- 然后，我们继续将 right 向右移动，寻找下一个可能的最小覆盖子串，重复上述过程，直到 right 到达 s 的末尾。
- 优化思路：我们可以在更新窗口时，利用一个变量 curLen 来记录当前窗口的长度，而不是每次都计算 right - left + 1。这样可以减少一些不必要的计算开销，提高算法效率。

💻代码实现（以 C++ 为例）

string minWindow(string s, string t) {// 用于记录字符串t中每个字符出现次数的哈希表int hash1[128] = {0};  // 用于记录当前窗口中每个字符出现次数的哈希表int hash2[128] = {0};  int kinds = 0, minlen = INT_MAX, begin = -1;// 统计字符串t中不同字符的种类数kinds，并记录每个字符的出现次数到hash1中for (auto c : t) {if (hash1[c] == 0) kinds++;hash1[c]++;}// 滑动窗口的左右指针left和right，以及用于统计当前窗口中满足t中字符出现次数要求的字符个数countfor (int left = 0, right = 0, count = 0; right < s.size(); right++) {char in = s[right];// 将进入窗口的字符in在hash2中的计数加1，并判断是否达到t中该字符的出现次数要求，如果达到则count加1if (++hash2[in] == hash1[in]) count++;// 当窗口内满足要求的字符个数count等于t中不同字符的种类数kinds时，尝试缩小窗口while (count == kinds) {// 如果当前窗口大小小于最小子串长度minlen，则更新minlen和beginif (right - left + 1 < minlen) {minlen = right - left + 1;begin = left;}char out = s[left++];// 如果移除窗口左侧字符out后，该字符在hash2中的计数小于t中该字符的出现次数要求，则count减1if (hash2[out] == hash1[out]) count--;hash2[out]--;}}// 如果begin仍为-1，表示没有找到符合要求的子串，返回空字符串；否则返回找到的最小子串if (begin == -1) return "";else return s.substr(begin, minlen);
}

希望通过今天对这两道题目的讲解，大家能对滑动窗口算法在处理字符串相关问题时有更深入的理解。滑动窗口算法通过巧妙地维护一个窗口，在遍历字符串的过程中高效地找到满足条件的子串，其思想在很多算法问题中都有广泛的应用。大家可以多做一些相关练习，加深对这种算法的掌握。如果在学习过程中有任何疑问，欢迎随时交流探讨😃。