前言
滑动窗口一般主要用于解决子数组或子串问题，这类的题目更看重对题目的分析和转化。
一、原理
在整个数组上，用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-1
return 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这个条件的种类。当种类比需要的大时，让窗口缩小，最后当满足的种类等于需要的种类数时，统计答案。
总结
滑动窗口的这些题确实很难，得多见多想，将复杂问题转化成简单问题。