滑动窗口详解

滑动窗口本质其实也是一种双指针算法，只是因为它维护的区间随着遍历的进行在不停变化，所以形象地称为“滑动窗口”

一、⻓度最⼩的⼦数组

 题目要求找到满足条件的长度最小的子数组，我们先来想想暴力的做法，再来想想能不能优化，一般来说，这种找子数组的暴力，就是两层for循环枚举左右两个端点，找到符合条件的所有子数组，然后找出最小值，下面画个图给大家分析一下

 代码如下

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ans=nums.size()+1;for(int left=0,right=0,s=0;right<nums.size();right++){//进窗口s+=nums[right];//判断是否需要出窗口while(s>=target){//更新答案ans=min(ans,right-left+1);s-=nums[left++];}}return ans==nums.size()+1?0:ans;}
};

通过这道题，我们就能总结出一些规律，滑动窗口的题目分为三个步骤，进窗口，判断是否出窗口以及何时更新答案，当然前提是你得先判断出这题是用滑动窗口解

二、将x减到0的最⼩操作数

这题如果你开始模拟左右两个区间之和==x，而没有想过转化条件，那它就会很难解决，但是其实题目可以等价成找元素和==sum(nums)-x的最长子数组的长度，最后用数组长度减去最长子数组长度就能得到最小操作数，而等价后的题目明显和上一道题几乎一样，这里就不具体分析了

代码如下

class Solution {
public:int minOperations(vector<int>& nums, int x) {int n=nums.size();int target=accumulate(nums.begin(), nums.end(), 0)-x;if(target<0) return -1;//注意判断边界条件int ans=n+1;for(int left=0,right=0,s=0;right<nums.size();right++){//进窗口s+=nums[right];//判断是否出窗口while(s>target) s-=nums[left++];//更新答案if(s==target) ans=min(ans,n-(right-left+1));}return ans==n+1?-1:ans;}
};

好，经过上面的题目，我们就已经对滑动窗口的题目更多的认识和了解，关键在于发现题目可以用滑动窗口解决以及维护区间的某些属性，同时两个指针往同一方向移动(即满足某种单调性)---滑动窗口的特征

三、⽔果成篮
 

这道题目就是维护区间内水果类型是否大于2，思路如下

 进窗口-判断是否出窗口-更新答案 的细节在下面的代码里(请细品)

class Solution {
public:int totalFruit(vector<int>& fruits) {int n=fruits.size(),ans=0;int cnt[n];memset(cnt,0,sizeof(cnt));for(int left=0,right=0,s=0;right<n;right++){//进窗口if(++cnt[fruits[right]]==1)//出现次数为1次，说明水果种类增加s+=1;//判断是否出窗口while(s>2){if(--cnt[fruits[left++]]==0)//出现次数为0次，说明水果种类减少s-=1;}ans=max(ans,right-left+1);}return ans;}
};

四、找到字符串中所有字⺟异位词

 这题跟上面几题不太一样，这题的窗口长度是固定的，就是查看字符串s中p.size()的窗口有几个是和组成p的字符一样，记录下标，步骤还是 进窗口-判断是否出窗口-更新答案 

代码如下

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int>ans;int hash1[26]={0},hash2[26]={0},k=p.size(),cout=0;for(int i=0;i<p.size();i++)hash1[p[i]-'a']++;for(int left=0,right=0;right<s.size();right++){//进窗口char in=s[right];//如果加完之后该字符的数量任然<=p中该字符的数量，说明增加的是有效字符，cout++if(++hash2[in-'a']<=hash1[in-'a']) cout++;//出窗口if(right-left+1>k){char out=s[left++];//如果该字符的个数本就<=p中该字符的数量，说明减少的是有效字符，cout--if(hash2[out-'a']--<=hash1[out-'a'])cout--;}//更新答案if(k==cout) ans.push_back(left);}return ans;}
};

 总结：牢记滑动窗口的三个步骤：进窗口，判断是否出窗口以及何时更新答案，稍难的滑动窗口一般都是和哈希表结合起来，主要是在判断进窗口和出窗口的条件上下文章，当然一切的前提是你能想到用滑动窗口来解决问题，当问题和维护一段连续区间的属性有关时，我们就可以想一想滑动窗口