【优选算法】Sliding-Chakra：滑动窗口的算法流（下）

文章目录

• 1.水果成篮
• 2.找到字符串中所有字母异位词
• 3.串联所有单词的子串
• 4.最小覆盖子串
• 希望读者们多多三连支持
• 小编会继续更新
• 你们的鼓励就是我前进的动力！

本篇接上一篇滑动窗口算法，这一篇有些许难度，为了提升自我，请耐心看完后，多敲代码整理思路，相信能够有莫大的收获😼

1.水果成篮

✏️题目描述：

✏️示例：

传送门：水果成篮

题解:

首先解读题意，简单来说就是找到一个区间，其中的果树种类用数字表示，种类不超过两种，题目默认是能找到至少两种水果，所以求在此前提下能找到的最长区间是多少？

💻第一步：

或许该题可以使用暴力解法解决，但明显时间复杂度太高无法通过示例
因此根据前些题目的经验，由于是找区间，而且要统计种类数量，滑动窗口＋哈希表

💻第二步：

具体的窗口滑动如图所示

先让第一个数据录入，即进窗口，判断不断循环，然后right依次向后移并不断往哈希表录入每个位置种类和更新数据，直到哈希表内的键值对大于2，即种类大于2；此时left减去第一个数据，即出窗口，判断不断循环，然后不断向后移直到哈希表里的一个种类数据变为0，对其进行erase操作减少一个种类，再次开始更新数据

💻代码实现:

#include #include #include using namespace std;class Solution{public: int totalFruit(vector<int>& fruits) { unordered_map<int, int> hash; int ret = 0, n = fruits.size(); for (int left = 0, right = 0; right < n; ++right) { hash[fruits[right]]++; 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.找到字符串中所有字母异位词

✏️题目描述：

✏️示例：

传送门：找到字符串中所有字母异位词

题解:

首先我们要知道什么是异位词？

本题第一难为解读题意，通常读不懂题目时要多结合示例分析，结合示例1和示例2，把p这个字符串放在s这个字符串里比对，不考虑p的顺序，找到所有异位词，返回其起始下标

💻第一步：

先思考如何在代码运行过程中判断其是否为异位词，只判断个数显然是不行的，既要种类相同，又要出现的个数相同，因为哈希表会减慢运行，这里也只有26种字母，所以我们可以给需要找到的字符串创建模拟哈希表hash1，被寻找的字符串创建模拟哈希表hash2，对比两个哈希表的种类及数量就能准确得出是否为异位词

💻第二步：

具体实现的流程图如图所示，与前些写的题有些许不同

先让第一个数据录入，即进窗口，判断不断循环，然后right依次向后移并不断往哈希表中录入，直到left和right之间的长度大于字符串p；此时left减去第一个数据，即出窗口，判断不断循环，然后向后移1位使长度继续维持为字符串p，check然后如果符合要求则更新结果。然后right向前一位，判断，left向前一位，判断更新结果，以此循环

💻细节问题

这里重点在于如何更新结果，一般的思路是遍历hash1和hash2，并对比两个数组，显然此方法是冗余复杂的，接下来将介绍一种方法，通常想不到，因此很有学习价值

先统计字符串p中的字符种类及数量，count表示s中left和right之间的种类数量，在right移动过程中，字符串s的起始种类数量都为0，然后当字符串s的种类数量小于等于字符串p的种类数量时，说明该位置增加的是有效字符，count++

还是滑动窗口的起始操作，如图当right到e时，明显超出了字符串p的大小，left应该在c，移动left到b，然后当字符串s的种类数量小于等于字符串p的种类数量时，说明该位置减少的是有效字符，count--

最后当两个模拟哈希表中的种类数量相等，即count == m

💻代码实现:

#include #include using namespace std;class Solution {public: vector<int> findAnagrams(string s, string p) { vector<int> ret; int hash1[26] = { 0 }; for (auto ch : p) { hash1[ch - \'a\']++; } int hash2[26] = { 0 }; int n = s.size(); int m = p.size(); for (int left = 0, right = 0, count = 0; right < n; ++right) { hash2[s[right] - \'a\']++; if (hash2[s[right] - \'a\'] <= hash1[s[right] - \'a\']) { count++; } if (right - left + 1 > m) { if (hash2[s[left] - \'a\'] <= hash1[s[left] - \'a\']) {  count--; } hash2[s[left] - \'a\']--; left++; } if (count == m) { ret.push_back(left); } } return ret; }};

3.串联所有单词的子串

✏️题目描述：

✏️示例：

传送门：串联所有单词的子串

题解:

本题的题意也有些难以理解，但是结合找到字符串中所有字母异位词这题的铺垫，使得这题也不是无从下手

如图所示，把这些字符串看成一个个的字符，是不是就和之前那题是一样的？

💻细节问题

w每个字符串的长度多长，那么left，right就有几种起始情况

当right移动到最后不足字符串w的长度时，会发生越界，所以要写为right + len <= n

💻代码实现:

#include #include #include using namespace std;class Solution {public: vector<int> findSubstring(string s, vector<string>& words) { unordered_map<string, int> hash1; for (auto s : words) { hash1[s]++; } vector<int> ret; int len = words[0].size(), m = words.size(), n = s.size(); for (int i = 0; i < len; ++i) { unordered_map<string, int> hash2; for (int left = i, right = i, count = 0; right + len <= n; right += len) { string in = s.substr(right, len); hash2[in]++; if (hash1.count(in) && hash2[in] <= hash1[in]) {  count++; } if (right - left + 1 > len * m) {  string out = s.substr(left, len);  if (hash1.count(out) && hash2[out] <= hash1[out])  { count--;  }  hash2[out]--;  left += len; } if (count == m) {  ret.push_back(left); } } } return ret; }};

4.最小覆盖子串

✏️题目描述：

✏️示例：

传送门：最小覆盖子串

题解:

本题题意为在字符串s里找到一个含有t的字符串区间，只要该区间内符合t的种类数量即可，无论其他的字符有多少个

💻细节问题

所以本题虽说是困难难度，但是依据前几题的思路铺垫，这道题也能说不在话下了，依旧是模拟哈希表+滑动窗口（因为哈希表太占空间了，影响效率）

注意当是当hash2中的种类数量和hash1中的种类数量一样时才count++

💻代码实现:

#include #include using namespace std;class Solution {public: string minWindow(string s, string t) { int hash1[128] = { 0 }; int kinds = 0; for (auto ch : t) { if (hash1[ch]++ == 0) { kinds++; } } int hash2[128] = { 0 }; int n = s.size(), minlen = INT_MAX, begin = -1; for (int left = 0, right = 0, count = 0; right < n; ++right) { if (++hash2[s[right]] == hash1[s[right]]) { count++; } while (count == kinds) { if (right - left + 1 < minlen) {  minlen = right - left + 1;  begin = left; } if (hash2[s[left]]-- == hash1[s[left]]) {  count--; } left++; } } if (begin == -1) { return \"\"; } else { return s.substr(begin, minlen); } }};

也是第一次用时击败100%，比官方还优秀的解法😎

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！