算法——滑动窗口（day7）

904.水果成篮 

904. 水果成篮 - 力扣（LeetCode）

 题目解析：

根据题意我们可以看出给了我们两个篮子说明我们在开始采摘到结束的过程中只能有两种水果的种类，又要求让我们返回收集水果的最大数目，这不难让我们联想到题目的另一层意思：求最长连续子数组，条件为不超过两种水果种类。

老规矩，我们先用暴力解法寻找优化过渡到滑动窗口。

right在遍历的过程中不仅要记录水果种类还需要记录个数，所以这里我们用哈希表作为辅助，当我们水果种类超出限制时那说明得进行第二轮的对比了。第二轮开始left往前一位，那么right是否也要复位呢？——不需要，因为第二轮right复位开始也只有两种结果，要么水果种类不变，要么水果种类变小，所以是完全没必要复位的，留在原位即可。而这个优化也引出了我们的滑动窗口算法。

算法解析：

滑动窗口流程图：

只要水果种类还没超标，那就让right继续遍历的同时用hash记录数据。当水果种类超标的时候就移动left减少水果数量，直到有一种类的水果数量为0删除该种类即可继续收录新的水果种类。最后记录长度完成解答。

代码：

class Solution {
public:int totalFruit(vector<int>& fruits) {//建立哈希表<水果种类，水果数量>unordered_map<int, int>hash;int n = fruits.size();int ret = INT_MIN;for (int left = 0, right = 0; right < n; right++){//种类不足，扩充窗口（移动right）以及哈希表收集数据hash[fruits[right]]++;//若种类仍不足则跳到下一循环开始扩充窗口//若超出种类，缩小窗口while (hash.size() > 2){//减掉对应种类上的数量hash[fruits[left]]--;//判断当水果数量为0时删除该种类if (hash[fruits[left]] == 0){hash.erase(fruits[left]);}//移动left，缩小窗口left++;}//记录长度ret = max(ret, right - left + 1);}return ret;}
};

用数组模拟哈希表版本： 

class Solution {
public:int totalFruit(vector<int>& fruits) {//数组模拟哈希表int hash[100000] ={0};//记录种类int kind = 0;int n = fruits.size();int ret = INT_MIN;for (int left = 0, right = 0; right < n; right++){if(hash[fruits[right]]==0) kind++;hash[fruits[right]]++;//若种类仍不足则跳到下一循环开始扩充窗口//若超出种类，缩小窗口while (kind > 2){//减掉对应种类上的数量hash[fruits[left]]--;//判断当水果数量为0时删除该种类if (hash[fruits[left]] == 0){kind--;}//移动left，缩小窗口left++;}//记录长度ret = max(ret, right - left + 1);}return ret;}
};

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

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

题目解析：

本题难点之一就在于异位词，但我们总不可能列举所有的情况来一一对比，这肯定是会超时的。

所以我们转换一下思路：用哈希表记录字符串p里面各个字符出现的次数。然后再用另一个哈希表记录字符串s中一定范围内各个字符出现的次数。最终对比两哈希表推出正确结果。

所以最终问题转换为：遍历整个字符串，找出两哈希表一致的子串，记录起始位置。

我们在这里由于字符串p的限定只能3个字符串3个字符串进行判定，不满足字符个数时right开始移动遍历并让哈希表辅助记录字符个数。当遍历的字符个数刚好时（这里为ccb,3个字符）对比两个哈希表，无论结果如何进入第2轮。

那么第二轮开始时right是前进好呢？还是复位？——前进（过渡到滑动窗口），因为前面已经录入哈希表中了，复位还得重新修改哈希表得不偿失。然后left前进之前删减哈希表数据并保持窗口长度，以此类推最后返回结果。~

算法解析：

本题与之前接触过的题都有些许不同，其一是这次的滑动窗口是固定长度的，其二是运用了两个哈希表进行辅助~

除此之外还需要介绍一下如何对比两个哈希表：

我们定义一个count变量来作为hash1中的有效个数（两表中能相对应的字符个数）

滑动窗口流程图：（因为步骤有点多，草草画一下）

 一些常规操作咱们就不讲了，这里主要来说一下：

当我们要录入hash1的时候需要判断录入的字符是否为有效个数（count)，判断方法就是如果在hash1中该字符个数<=hash2中该字符个数，那就说明在录入后能够成为与hash2抵消该字符个数的可能，则count+1。

当我们要删减hash1的时候需要判断删减的字符在删减后是否影响有效字符个数，我们拿(c,c,b,a)举例，假如我们要删除第一个c的时候那么hash1里面的c还能和hash2里的c抵消吗？——可以的，那么就说明有效个数不会变，即hash1中该字符个数<hash2中该字符个数，count才会变化，因为在小于的时候无法抵消。

代码：

class Solution {
public:vector<int> findAnagrams(string s, string p) {//记录字符串s的数据unordered_map<int, int>hash1;//记录字符串p的数据unordered_map<int, int>hash2;vector<int> ret;//录入p数据for (auto ch : p){hash2[ch - 'a']++;}//记录字符串p中字符个数int m = p.size();//有效个数（用于抵消hash2)int count = 0;for (int left = 0, right = 0; right < s.size(); right++){//把字符串s中的字符录入hash1中hash1[s[right] - 'a']++;//判断录入字符是否为有效个数if (hash1[s[right] - 'a'] <= hash2[s[right] - 'a']){//如果发现该字符有增长到抵消hash2的可能，即为有效个数count++;}//判定结束先观察窗口长度，如果长度不够则跳到下一循环扩充窗口//如果窗口长度过长，缩小窗口if (right - left + 1 > m){//先删减hash1中的字符个数hash1[s[left] - 'a']--;if (hash1[s[left] - 'a'] < hash2[s[left] - 'a']){//如果发现在删减后出现无法抵消hash2中字符的可能，则减小该有效个数count--;}//缩小窗口left++;}//这里减完长度肯定达到标准了，可以开始对比两哈希表是否一致if (count == m){//hash1中的有效个数可以抵消掉hash2中个数，记录结果ret.push_back(left);}}return ret;}
};