【算法一周目】滑动窗口（2）

class Solution { public: int totalFruit(vector<int>& fruits) { // 统计滑动窗口内水果的种类和数量 unordered_map<int, int> hash; int n = fruits.size(), ret = 0; for(int left = 0, right = 0; right < n; right++) { //进窗口，将水果加入hash表 hash[fruits[right]]++; //若水果种类超过2，收缩窗口直到种类不超过2 while(hash.size() > 2) { hash[fruits[left]]--; if(hash[fruits[left]] == 0) hash.erase(fruits[left]); left++; } //更新结果 ret = max(ret, right - left + 1); } return ret; } };

2.使用数组模拟hash表

题目其实有提到 fruits[i] 的范围，所以我们不必真的使用unordered_map作为hash表，使用数组模拟即可，这样虽然会浪费空间，但是提高了效率。

class Solution { public: int totalFruit(vector<int>& fruits) { int hash[100000] = { 0 }; //cnt用于统计hash表的水果的种类个数 int n = fruits.size(), ret = 0, cnt = 0; for(int left = 0, right = 0; right < n; right++) { hash[fruits[right]]++; if(hash[fruits[right]] == 1) cnt++; while(cnt > 2) { hash[fruits[left]]--; if(hash[fruits[left++]] == 0) cnt--; } ret = max(ret, right - left + 1); } return ret; } };

时间复杂度：O(n)

空间复杂度：O(n)

找到字符串中所有字母异位词

题目链接：438. 找到字符串中所有字母异位词

题目描述：

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。顺序可以不考虑。

异位词是指由相同字母重排列形成的字符串（包括相同的字符串）。

解题思路

解法：滑动窗口 + 哈希

因为字符串 p 的异位词的长度一定于字符串 p 的长度相等，所以我们可以在字符串 s 中使用与字符串 p 等长度的滑动窗口来求解。

我们可以使用两个大小为26的数组来模拟哈希表，用于统计窗口内的字母频次和字符串s的字母频次，当比较得到两个哈希表相等时，说明滑动窗口中每种字母的数量与字符 p 每种字母的数量相同，窗口内的字符是字符 p 的一个异位词，此时记录窗口起始索引。

具体过程如下：

1.初始化 left 和 right 指针来维护滑动窗口，两个大小为26的数组 hash1 和 hash2 来模拟哈希表，记录字符串 p 的字母频次和窗口字母频次。

2.right 向右遍历数组right 位置的字母入窗口，将其加入哈希表。当滑动窗口长度大于字符串 p 的长度时，left++，将窗口左侧字母移除同时更新其在哈希表的频次。

3.更新结果，当 hash1 与 hash2 相等时，记录窗口起始索引。

注意：判断两个 hash 表是否相等的时间复杂度较高，效率较低。故我们要优化更新结果的判断条件（两个哈希表相等），我们可以来使用一个变量 cnt 记录窗口内的字母相较于字符串 p 的有效字符的数量，并在入窗口和窗口时维护 cnt，这样更新结果时，只需判断 cnt 是否等于字符串 p 的长度就可以知道窗口字符是否是字符串 p 的异位词。

解释下有效字符的数量，其实就是让窗口的组成字母尽可能接近字符 p ，当有效字符的数量等于字符 p 的长度，就说明了窗口的字母频次与字符 p 的字母频次相等，这也是比较两个统计字母频次的哈希表相等的本质，cnt 间接完成了这个任务。

代码实现

class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> ret; int n = s.size(), m = p.size(); //统计p字符串中每个字母出现的个数 int hash1[26] = { 0 }; for(auto ch : p) hash1[ch - 'a']++; //统计窗口中每个字母出现的个数 int hash2[26] = { 0 }; //统计窗口中有效字符的数量 int cnt = 0; for(int left = 0, right = 0; right < n; right++) { //进窗口 + 维护cnt char in = s[right]; hash2[in - 'a']++; if(hash2[in - 'a'] <= hash1[in - 'a']) cnt++; //窗口长度大于字符串p的长度，窗口左端字母出窗口， //并更新cnt和哈希表 if(right - left + 1 > m) { char out = s[left++]; //出窗口 + 维护cnt if(hash2[out - 'a'] <= hash1[out - 'a']) cnt--; hash2[out - 'a']--; } //更新结果 if(cnt == m) ret.push_back(left); } return ret; } };

时间复杂度：O(n)

空间复杂度：O(1)

串联所有单词的子串

题目链接：30. 串联所有单词的子串

题目描述：

给定一个字符串 s 和一个字符串数组 words，words 中所有字符串的长度相同。s 中的串联子串是指包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果words= ["ab","cd","ef"]，那么 "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" 和 "efcdab" 都是串联子串，而 "acdbef" 不是串联子串，因为它不是 words 排列的连接。

返回所有串联子串在 s 中的开始索引，顺序可以不考虑。

解题思路

解法：滑动窗口 + 哈希表

这道题就是找到字符串中所有字母异位词的升级版，从原来处理单个字符变成了处理单个单词，我们只需要将 words 的单词看成单个字母就行了，然后用滑动窗口 + 哈希表解决。

具体过程：

1.用哈希表 hash1 记录 words 中每个单词的频次。

2.遍历字符串 s ，并用哈希表 hash2 来维护滑动窗口内的单词频次，注意每次增加窗口的大小为单词的长度。

3.当窗口大小大于所有单词的总长度时，出窗口和更新 hash2 。

4.当 hash1 和 hash2 两个哈希表相等时，更新结果。

判断两个哈希表是否相等消耗较大，用 count 来优化，count 统计滑动窗口内有效单词的个数。当 count 与 words 的单词个数相等时，说明找到了符合条件的一个窗口。

代码实现

class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int> ret; unordered_map<string, int> hash1; for(auto& e : words) hash1[e]++; int len = words[0].size(), m = words.size(), n = s.size(); //执行len次滑动窗口 for(int i = 0; i < len; ++i) { unordered_map<string, int> hash2; for(int left = i, right = i, count = 0; right <= n - len; right += len) { //进窗口+维护count string in(s.begin() + right, s.begin() + right + len); hash2[in]++; if(hash1.count(in) && hash2[in] <= hash1[in]) count++; //判断+出窗口+维护count if(right - left + 1 > m * len) { string out(s.begin() + left, s.begin() + left + len); if(hash1.count(out) && hash2[out] <= hash1[out]) count--; hash2[out]--; left += len; } //更新结果 if(count == m) ret.push_back(left); } } return ret; } };

1.执行 len 次滑动窗口（len 是单词长度）：由 s 字符串的长度不一定是单词长度的整数倍，需要执行 len 滑动窗口来保证答案的完整性。

2.注意 right 的范围，right 最后一次执行循环的位置应该是在 n - len 处。

时间复杂度：O( n * len)，其中 n 是字符串 s 的长度，需要 len 次滑动窗口，每次遍历一次 s。

空间复杂度：O(m * len)，m 是单词个数，每次滑动窗口都需要用一个哈希表来存储单词频次。

最小覆盖子串

题目链接：76. 最小覆盖子串

题目描述：

给你一个字符串 s 和一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在这样的子串，则返回空字符串 ""。

注意：

对于 t 中重复的字符，最小子串中该字符数量必须不少于 t 中的字符数量。
如果存在这样的子串，答案是唯一的。

解题思路

解法：滑动窗口+哈希

根据题目，我们直接根据暴力解法来优化，就得到滑动窗口+哈希的解题方法。

具体过程如下：

1.利哈希表hash1来统计字符串 t中每个字符出现的频次。

2.使用滑动窗口遍历字符串 s ，并用哈希表 hash2 来统计窗口中字符频次。

3.当窗口的字符频次满足要求时，更新结果，然后收缩窗口，直到窗口字符频次不满足要求。

注意：这里判断窗口的字符频次满足要求不是判断两个哈希表是否相等，而是 hash1 的字符频次要完整的出现在 hash2 中，hash1 中可以出现除字符串 t 中的字符以外的字符频次。也就是说，窗口内只要完整出现字符串 t 的所有字符即可（字符种类及其对应的频次）。

我们这里还是利用 count 来完成判断，这里的 count 统计的时有效字符的种类，只有 t 中的单个字符在窗口内出现的频次与在 t 中完全一样，count 才自增1，同理，频次不相等时就自减 1，当 count 与 t 中字符种类数相同时，说明找到一个符合条件的覆盖字串，更新结果。

代码实现

class Solution { public: string minWindow(string s, string t) { string ret; //hash1统计t字符频次和计算hash1的大小，hash1size统计t的字符种类 int hash1[128] = { 0 }, hash1size = 0; for(auto e : t) if(hash1[e]++ == 0) hash1size++; //hash2统计窗口字符频次 int hash2[128] = { 0 }; int len = INT_MAX, start = 0; //count统计有效字符的种类 for(int left = 0, right = 0, count = 0; right < s.size(); right++) { //进窗口 + 维护count char in = s[right]; if(++hash2[in] == hash1[in]) count++; //判断 while(count == hash1size) { //更新结果 if(right - left + 1 < len) { len = right - left + 1; start = left; } //出窗口+维护count char out = s[left++]; if(hash2[out]-- == hash1[out]) count--; } } ret = len == INT_MAX ? "" : s.substr(start, len); return ret; } };

时间复杂度：O(n)

空间复杂度：O(1)

拜拜，下期再见😏

摸鱼ing😴✨🎞