1.何为滑动窗口？

     滑动窗口其实也是一种算法，主要有两类：一类是固定窗口，一类是可变窗口。固定的窗口只需要一个变量记录，而可变窗口需要两个变量。

2.固定窗口

     就像上面这个图一样。两个相邻的长度为4的红色窗口，下一个窗口一定比前一个窗口少一个数据，以及多一个数据。

      橙色为切换窗口时少的那个数据，黄色为多出来的那个数据，所以可以直接沿用之前数据，并且减去橙色数据，加上黄色数据，就是下一个窗口的值了。这就是滑动窗口的一个经典思路。

2.1 例题解析

      首先题是这样的

给你一个整数数组arr和两个整数k和target。请你返回长度为k且平均值大于等于target的子数组数目。

       我们可以看到他已经确定了窗口的长度，像这种滑动窗口的问题，一般都是连续字串和连续子数组的问题，在我做过的题中还没有例外，这也是滑动窗口的应用限制，必须连续。下面让我们看看怎么写：

       (1)首先，统计前k个数的和sum，作为第一个窗口的值，并且判断是否满足sum>=target，如果满足，则计数器加一；

       (2)然后，窗口开始右移，以后每次通过前一个相邻窗口，计算得到下一个窗口的值，并且判断条件是否满足满足则计数器加一；

       (3)返回计数器的值；

nclude<iostream>
int numOfSubarrays(int* arr, int arrSize, int k, int target)
{int r;int sum = 0;int cnt = 0;for (r = 0; r < k; r++){sum += arr[r];}if (sum >= target)cnt++;for (r = k; r < arrSize; r++){sum -= arr[r - k];sum += arr[r];if (sum >= target)cnt++;}return cnt;
}

2.2 leetcode固定窗口题目及模板总结

2.2.1 定长字串中元音的最大数目  

class Solution {
public:int check(char c)//每次遇到一个字符都需要进行判断，所以我们自己实现一个函数，避免重复代码{if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'){return 1;}return 0;}int maxVowels(string s, int k) {int n=s.size();int r=0;//窗口边界int cnt=0;//计数器int sum=0;//比较迭代的变量for(;r<n;r++)//开始遍历{cnt+=check(s[r]);//向窗口内添加元素if(r>=k)//窗口长度大于给定值{cnt-=check(s[r-k]);滑动直到长度等于k，减去左边元素，向右不断滑动}sum=max(sum,cnt);//将sum和cnt的值进行比较，这里sum其实起到了比较作用，将cnt的值存储到sum中}return sum;}
};

2.2.2 长度最小的子数组

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int r;int result=INT32_MAX;int sum=0;int i=0;for(r=0;r<nums.size();r++){sum+=nums[r];while(sum>=target){result=min(result,r-i+1);sum-=nums[i++];}}return result==INT32_MAX?0:result;}
};

       从这两道题中我们看到了一些相似的代码，这就是

2.2.3 固定窗口长度模板

int subarrays(int* arr, int k, int target)
{ int n=arr.size();//数组长度int r;//窗口边界int cnt = 0;//一般用来求和或者计数，视题目而定int sum = 0;//比较迭代的变量for (; r < n; r++)//开始遍历{cnt += arr[r];//向窗口内添加元素if (r >= k)//窗口长度大于给定值{cnt -= arr[r - k]; //减去左边元素，向右不断滑动，直到长度等于k}sum = max(sum, cnt);//更新sum的值，将sum和cnt的值进行比较，这里sum其实起到了比较作用，将cnt的值存储到sum中}return sum;
}

3.非固定窗口

3.1 例题解析

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

     这个题怎么写呢？这个可没有说求固定长度，你翻转最多k个0之后连续1的长度最大，这个长度就是数组中连续1的最大个数，那我们就把固定长度不固定就ok了啊，下面看代码解析：

int longestOnes(vector<int>& nums, int k) {int n=nums.size();//数组/字符串长度int sum=0;//用于统计子数组/子区间是否有效，看题目要求，可能是求和/计数int l=0;//双指针，代表遍历的区间int zerocnt=0;//统计0的个数for(int r=0;r<n;r++){if(nums[r]==0)zerocnt++;//满足题目要求，计数器+1while(zerocnt>k)//翻转0的个数大于k{if(nums[l++]==0)zerocnt--;//那就开始滑动窗口了，左边界开始滑动，这时候需要判断左边界的数是不是0，是0则计数器-1，滑动到计数器的值等于k}sum=max(sum,r-l+1);//更新sum的值}return sum;}
};

     相信看完代码之后大家会发现，固定长度的滑动窗口，while循环的条件都是比较长度，而非固定长度的滑动窗口，虽然不是比较长度，但也有其他的条件进行限制，具体什么条件就需要看具体的题目了。

3.2 leetcode非固定窗口题目及模板总结

3.2.1 字符串的排列

class Solution {
public:bool checkInclusion(string s1, string s2) {//滑动窗口unordered_map<char, int> win, need;//将子串的元素压入哈希表for (auto &i : s1){++need[i];}//定义边界int right = 0, left = 0, n = s1.size(), num = s2.size(), count = 0;//进行滑动窗口for(;right < num;right++){//如果可以在哈希表中找到元素就压入到窗口中if (need.find(s2[right]) != need.end()){++win[s2[right]];if (need[s2[right]] == win[s2[right]]){++count;}}while(right - left + 1 >= n){if (count == need.size()){return true;}//缩小窗口if (need.find(s2[left]) != need.end()){//缩小窗口的步骤其实跟扩大窗口的步骤是相反的if (need[s2[left]] == win[s2[left]]){--count;}--win[s2[left]];}left++;}}return false;}
};

3.2.2 最短超串

class Solution {
public:vector<int> shortestSeq(vector<int>& big, vector<int>& small) {int n=big.size();//数组长度unordered_map<int,int>win,need;//定义两个哈希表，一个存储子数组，一个存储窗口for(auto a:small)//将子数组压入哈希表中便于查找和比较{need[a]++;}int l=0,r=0;//定义双指针(变量)作边界vector<int>ans;//定义一个数组用来存储最短子数组的左端点和右端点int count=0;//计数器，用来计算长数组出现子数组元素的次数，便于条件处理int len=INT_MAX;//可以不断更新的长度len//开始滑动窗口for(;r<n;r++){//扩大窗口if(need.find(big[r])!=need.end()){win[big[r]]++;if(need[big[r]]==win[big[r]])//防止重复{count++;  }}//开始缩小窗口while(count==need.size()){//进行获取最短超串if(len>r-l+1)//判断下一个窗口是否比上一个窗口长度小，如果小则更新len和ans数组的值{ans={l,r};len=r-l+1;}如果此时窗口左端的值在子数组的哈希表中耀进行特殊处理if(need.find(big[l])!=need.end()){if(need[big[l]]==win[big[l]]){count--;}win[big[l]]--;}l++;}}return ans;}
};

3.3.3 非固定窗口模板

int slidingWindow(vector<int> nums) {int n = nums.size();int ans = 0;// 记录窗口内的元素及其个数，非必要map<int, int> um;// l：窗口左边界； r：窗口右边界int l = 0, r = 0;// r 指针负责探索新的区间，直到搜索到nums的某末尾for(;r < n;r++) {um[r]++;// 如果区间不满足条件，l指针右移，窗口收缩while (区间[l, r] is Invalid) {um[l]--;l++;}// 此处处理结果, deal with(ans, 区间[l, r])res = max(ans, r - l + 1); // 或者res = min(ans, r - l + 1);}return ans;
}