【优选算法】Sliding-Chakra：滑动窗口的算法流（下）
文章目录
本篇接上一篇滑动窗口算法，这一篇有些许难度，为了提升自我，请耐心看完后，多敲代码整理思路，相信能够有莫大的收获😼
1.水果成篮
✏️题目描述：
✏️示例：
传送门：水果成篮
题解:
首先解读题意，简单来说就是找到一个区间，其中的果树种类用数字表示，种类不超过两种，题目默认是能找到至少两种水果，所以求在此前提下能找到的最长区间是多少？
💻第一步：
或许该题可以使用暴力解法解决，但明显时间复杂度太高无法通过示例
因此根据前些题目的经验，由于是找区间，而且要统计种类数量，滑动窗口＋哈希表
💻第二步：
具体的窗口滑动如图所示
先让第一个数据录入，即进窗口，判断不断循环，然后right依次向后移并不断往哈希表录入每个位置种类和更新数据，直到哈希表内的键值对大于2，即种类大于2；此时left减去第一个数据，即出窗口，判断不断循环，然后不断向后移直到哈希表里的一个种类数据变为0，对其进行erase操作减少一个种类，再次开始更新数据
💻代码实现:
#include<iostream>#include<vector>#include<unordered_map>usingnamespace std;classSolution{public:inttotalFruit(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<iostream>#include<vector>usingnamespace std;classSolution{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<iostream>#include<vector>#include<unordered_map>usingnamespace std;classSolution{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<iostream>#include<string>usingnamespace std;classSolution{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%，比官方还优秀的解法😎
希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力！
