数据结构与算法：滑动窗口

前言

滑动窗口一般主要用于解决子数组或子串问题，这类的题目更看重对题目的分析和转化。

一、原理

在整个数组上，用l和r分别控制窗口的左右边界，r++就扩大，l++就减小。

当窗口的范围和题目中某个指标间存在单调关系时，就可以考虑使用滑动窗口解决，整个过程一般会需要用某种数据结构或算法来维护信息，每次统计的就是子数组以每个位置开头或结尾的答案。

二、题目

1.无重复字符的最长子串

class Solution {
public:int lengthOfLongestSubstring(string s) {map<int,int>mp;map<int,int>::iterator iter;int ans=0;for(int l=0,r=0;r<s.length();r++){iter=mp.find(s[r]);if(iter!=mp.end()){l=max(l,mp[s[r]]+1);}ans=max(ans,r-l+1); mp[s[r]]=r;}return ans;}
};

首先分析题目可以发现存在单调性：窗口越大，越可能出现重复字符。

之后，考虑重复这一性质，可以用一个哈希map来维护每个字符最晚出现的位置，这样当遇到重复的字符，直接让l跳到该字符上次出现位置的下一个位置即可。这里注意l只能往前跳！

2.长度最小的子数组

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

分析题目单调性：窗口越大，累加和越大。

于是考虑使用前缀和来维护子数组累加和，因为要求长度最小，所以若窗口缩小时累加和仍大于target，就让窗口缩小。

3.最小覆盖子串

class Solution {
public:string minWindow(string s, string t) {map<int, int> cnts;for (int i = 0; i < t.length(); i++) // 统计“欠”{cnts[t[i]]--;}int len = INT_MAX;int start = 0;for (int l = 0, r = 0, debts = t.length(); r < s.length(); r++) {if (cnts[s[r]]++ < 0) // 仍然“欠”{debts--; // 需要“还”的减少}if (debts == 0) // t中所有字符均满足{while (cnts[s[l]] > 0) // 尽量短{cnts[s[l]]--;l++;}if (len > r - l + 1) {len = r - l + 1;start = l;}}}return len == INT_MAX ? "" : s.substr(start, len);//substr第二个参数是取几个！}
};

 这个题就非常需要思考了，这个思路确实很妙。

先分析单调性：窗口越大，子串越有可能符合包含t中每个字符的标准。

整体的思路是，为了统计子串中是否都包含了t中字符，所以可以从“欠”和“还”的角度考虑。

具体来说，先统计t中出现的字符，将其出现次数设置为“欠”，即子串还“欠”这些字符才能满足标准。之后，设置debts变量，表示一共“欠”的字符个数，若新加入的字符是“欠”的状态，就让debts减1。当debts等于0时，即不再“欠”字符了，就开始“还”。具体是只要窗口左侧字符处于“盈余”状态，就缩窗口，让子串尽量小。为了返回一个串，所以每次长度更新时记一下当前窗口左侧位置。

注意substr函数的第二个参数是取几个字符！！！

4.加油站

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n=gas.size();// vector<int>rest;// for(int i=0;i<2;i++)// {//     for(int j=0;j<n;j++)//     {//         rest.push_back(gas[j]-cost[j]);//     }// }for(int l=0,r=0,sum;l<n;l=r+1,r=l){sum=0;//while(sum+rest[r]>=0)while(sum+gas[r%n]-cost[r%n]>=0){       if(r-l+1==n){return l;}   //sum+=rest[r];sum+=gas[r%n]-cost[r%n];r++;}}return -1;}
};

 这个题的难点在于可以转一圈，暴力的做法就是开个两倍长度数组，简便方法是取r%n位置的数。

这个题用滑动窗口主要是题目的情景比较符合。

所以依然要用前缀和来维护剩余油量，当剩余大于0时，就一直往外扩，直到长度为n，即可以走一圈时返回此时窗口左边界，即起始位置。

5.替换子串得到平衡字符串

class Solution {
public:int balancedString(string s) {int n=s.length();map<int,int>cnts;for(int i=0;i<n;i++){cnts[s[i]]++;}int debts=0;for(map<int,int>::iterator iter=cnts.begin();iter!=cnts.end();iter++){iter->second=iter->second<n/4?0:n/4-iter->second;debts-=iter->second;//“欠”}//转化成“找最小覆盖子串”int ans=INT_MAX;for(int l=0,r=0;r<n;r++){if(cnts[s[r]]++<0){debts--;}if(debts==0){while(cnts[s[l]]>0){cnts[s[l]]--;l++;}ans=min(ans,r-l+1);}}return ans;}
};

 下面几个题就逐渐开始抽象起来了，分析难度越来越大，更考验对题目的转化。

这个题需要一步转化，先统计一遍各个字符的出现次数，然后将不够的当作“欠”，转化成求这些字符的“最小覆盖子串”。

6.K 个不同整数的子数组

class Solution {
public:int subarraysWithKDistinct(vector<int>& nums, int k) {//转化 -> 小于等于k-小于等于k-1return f(nums,k)-f(nums,k-1);}int f(vector<int>&nums,int k){map<int,int>cnts;int ans=0;for(int l=0,r=0,kinds=0;r<nums.size();r++){if(++cnts[nums[r]]==1){kinds++;}while(kinds>k){if(--cnts[nums[l]]==0){kinds--;}l++;}ans+=r-l+1;//0~3:0~3+1~3+2~3+3~3->四种}return ans;}
};

 首先分析题目，会发现等于k其实没有单调性，那就考虑将找等于k的个数转化成大于等于k-大于等于k-1的个数。因为窗口越大，大于等于k的子数组越长，有单调性。

之后就是在统计出现次数时统计种类，当种类大于k时让窗口缩小。最后要注意，滑动窗口每次统计的是子数组在此范围上以右边界结尾的答案，所以种类数即窗口长度。

7.至少有 K 个重复字符的最长子串

class Solution {
public:int longestSubstring(string s, int k) {int ans=0;for(int require=1;require<=26;require++){map<int,int>cnts;for(int l=0,r=0,kinds=0,satisfy=0;r<s.length();r++){cnts[s[r]]++;if(cnts[s[r]]==1){kinds++;}if(cnts[s[r]]==k){satisfy++;}while(kinds>require){if(cnts[s[l]]==1){kinds--;}if(cnts[s[l]]==k){satisfy--;}cnts[s[l]]--;l++;}if(satisfy==require){ans=max(ans,r-l+1);}}}return ans;}
};

这个题就更困难了，转化的这一步太难想了。

首先，需要分析出这个题里到底是谁存在单调性，分析可知，窗口越大时，字符种类越多。所以要找的子串即，只有1种字符大于等于k，只有2种字符大于等于k……只有26种字符大于等于k这些情况的最长子串的最大值。（太难想了这个思路）

所以枚举二十六个字母，每次都维护当前map里的字符种类和满足大于等于k这个条件的种类。当种类比需要的大时，让窗口缩小，最后当满足的种类等于需要的种类数时，统计答案。

总结

滑动窗口的这些题确实很难，得多见多想，将复杂问题转化成简单问题。

END