通过以下几道题来熟悉滑动窗口
滑动窗口3大问题：如何移入窗口，如何移出窗口，如何更新答案
209. 长度最小的子数组
我们考虑通过窗口来计算和，快慢指针从左开始遍历。
移入窗口：直接把当前元素加进来。
移出窗口：如果和大于target就把左边移出，看看窗口变小了还是否满足。
更新答案：在移出窗口前记录当前长度与之前的结果取min。
简单分析一下这样是否一定能得出正确答案：假设答案是数组中的某一段，那么这个答案一定是从砍去左端一点一点移出来的，也就是我们会找到最终结果。
代码如下：
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int sum = 0;int ant = INT_MAX;//存答案for (int i = 0, j = 0; i < n; i++) {sum += nums[i];//移入窗口while (i >= j && sum >= target) {//当前窗口满足题意了，看看变小是否满足ant = min(ant, i - j + 1);//更新答案sum -= nums[j++];//移出窗口}}return ant == INT_MAX ? 0 : ant;//ant没变过说明整个数组所有值加起来也到不了target，返回0}
};3. 无重复字符的最长子串
跟上一题有点像，上一题为最短，这题为最长。
我们想一下如何用滑动窗口3步来实现
移入窗口：把当前字符放入窗口
移出窗口：窗口中有重复字符时，移动左端，直到无重复字符
更新答案：无重复字符就与之前存的结果取max
简单分析一下这样是否一定能得出正确答案：假设答案是字符串中的某一段，那么这个答案左边第一个一定与窗口内字符相重，该操作也是我们移出窗口能得到的，也就是我们会找到最终结果。
代码如下：
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char, int> m;//统计窗口内字符种类和数量int n = s.size();int ant = 0; //答案for (int i = 0, j = 0; i < n; i++) {m[s[i]]++;//移入窗口while (j <= i && m[s[i]] > 1) {m[s[j]]--;//有重复的移出窗口j++;}ant = max(ant, i - j + 1);//更新答案}return ant;}
};76. 最小覆盖子串
这个题难度就来了，我们看看它比前两个难在哪，又该怎么处理
我们想一下，首先得遍历字符串t，看看它有多少种字符，每种字符有多少个。
然后遍历字符串s看看，哪一段满足且是最短的。如果s能覆盖t，那最长肯定是s，最短的情况是中间的某一段，也是可以通过窗口移出来的。
移入窗口：当前字符放进来，看看这个字符是否覆盖
移出窗口：如果所有字符都覆盖则移出左端看看是否还覆盖
更新答案：如果所有字符都覆盖就统计一下左右端点，取长度最小，最后截取一下字符串即可
代码如下：
class Solution {
public:string minWindow(string s, string t) {int ls = s.size();unordered_map<char, int> ms, mt;int left = -1, right = 100005; //存答案for (auto i : t)mt[i]++; //遍历一下看看每种字符有多少个int num = mt.size();//算算有多少种字符未被覆盖for (int i = 0, j = 0; i < ls; i++) {if (++ms[s[i]] == mt[s[i]])//当前字符加入窗口num--; //如果该字符被覆盖了则减1while (j <= i && num == 0) {//全覆盖了if (right - left + 1 > i - j + 1)//比较长度left = j, right = i;//更新答案if (--ms[s[j]] < mt[s[j]])num++;//移出窗口，移出后不覆盖则num++j++;}}return right - left > ls ? "" : s.substr(left, right - left + 1);//right-left为初始值则返回空字符串，否则截取所需字符串}
};这道题主要多了一步移入移出额外判断
134. 加油站
这道题用了环形数组，我们采用倍增来处理，并依然可以采用滑动窗口来解决。
我们想一下如果从某站开始无法绕一圈，那一定会在中间停下，这时我们只需把起始点去掉，从它的下一点开始看看能不能绕一圈，这就蕴含滑窗的思想。
移入窗口：加入当前站汽油，减去到下一站消耗汽油
移出窗口：如果汽油不够了，去掉起始站再判断。
更新答案：走的站数量为一圈的数量时，返回答案
代码如下：
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();int sum = 0; //sum大于0表示能到下一站gas.insert(gas.end(), gas.begin(), gas.end());//倍增处理循环cost.insert(cost.end(), cost.begin(), cost.end());for (int i = 0, j = 0; i < 2 * n; i++) {sum += gas[i] - cost[i];//移入窗口while (j <= i && sum < 0) {//移出窗口sum -= gas[j] - cost[j];//绕不了一圈，把起始减去j++;}if (i - j + 1 == n) return j;//如果长度为n则绕一圈了//更新答案，直接返回}return -1;}
};这个题有一个循环要求，我们可以倍增来解决
1234. 替换子串得到平衡字符串
我们想一下是要替换字符串，也就是窗口内字符串是不要的，那它有什么性质吗？能判断如何移出移入吗？简单想一下发现比较困难，所以我们转换思路，看看窗口外有什么性质。
我们发现如果要替换，则一定有字符长度大于l/4,而要替换的字符串一定包含这些，并只能大于等于它，那么外面的每种字符数量一定小于等于l/4,那么这时窗口内字符替换后一定能令整个字符串符合要求。
移入窗口：当前字符数量减1
移出窗口：窗口外字符都小于等于l/4时，缩小窗口看看还行不行，把左端字符加上
更新答案：窗口外字符都小于等于l/4时，统计答案，取min
代码如下：
class Solution {
public:int balancedString(string s) {int l = s.size();int n = l / 4; //算1/4长度 unordered_map<char, int> m;//每种字符数量int ant = l;//答案，初始化为最大值for (char i : s)m[i]++;//遍历，统计一下字符串每个字符有多少个if (c['Q'] == n && c['W'] == n && c['E'] == n && c['R'] == n)return 0;//如果已经满足了直接返回for (int i = 0, j = 0; i < l; i++) {--c[s[i]];//移入窗口，窗口外字符--while (j <= i && c['Q'] <= n && c['W'] <= n && c['E'] <= n && c['R'] <= n) {//窗口外字符少于l/4ant = min(ant, i - j + 1);//更新答案++c[s[j]];//移出窗口，窗口外字符++j++;}}return ant;}
};这道题我们需要考虑窗口外的性质，这又是一种处理方式。
map有时可以用普通数组替换，但这里为了让大家更好掌握滑动窗口的套路，我则都采用了map
992. K 个不同整数的子数组
这道题看起来没什么思路，如何处理k，我们想一下如果用滑窗处理k的话不成立，因为是否移出窗口不好处理，如果当前窗口大于k我们移出左端直到等于k，但这是再移出左端也有可能还等于k，如果又移动，则刚才的结果丢了，所以比较麻烦，但是如果我们算当前个数小于等于k是没问题的，如果窗口长为n，则答案可以加上n，表示包含最右端的子数组个数有K个。
我们只需算两遍，小于等于k与小于等于k-1的答案再做差即可。
移入窗口：当前数字放入窗口
移出窗口：如果种类多了，则移出左端
更新答案：加上以该元素为尾元素的符合要求的数组的数量
代码如下：
class Solution {
public:int subarraysWithKDistinct(vector<int>& nums, int k) {return f(nums, k) - f(nums, k - 1);//做差}int f(vector<int>& nums, int k) {unordered_map<int, int> m;//每种数字有多少个int n = nums.size();int ant = 0;//答案for (int i = 0, j = 0; i < n; i++) {m[nums[i]]++;//移入窗口while (j <= i && m.size() > k) {//数目多了减少if (--m[nums[j]] == 0) //移出窗口m.erase(nums[j]);j++;}ant += i - j + 1;//以i为最后元素的子数组有多少个}return ant;}
};这道题思路较为巧妙，也是解题的难点
395. 至少有 K 个重复字符的最长子串
这道题也不好想思路，但是我们发现只有小写字母，也就是26个，那么我们可以循环遍历，当子串只有1，2，3......26种字符时，有无符合题意得子串。
移入窗口：当前字符数量加1
移出窗口：当字符种类超过当前循环要求时，移出左端
更新答案：检查窗口内每个字符是否符合要求，符合就更新为更长得长度
代码如下：
class Solution {
public:int longestSubstring(string s, int k) {unordered_map<char, int> m;//统计每种字符数量int n = s.size();int ant = 0;//答案for (int num = 1; num <= 26; num++) {m.clear();//清空，当窗口内有num种字符for (int i = 0, j = 0; i < n; i++) {m[s[i]]++;//移入窗口while (j <= i && m.size() > num) {if (--m[s[j]] == 0)//移出窗口m.erase(s[j]);j++;}if ( check(m, k) )//符合要求，更新答案ant = max(ant, i - j + 1);}}return ant;}bool check(unordered_map<char, int>& m, int k) {for (auto i = m.begin(); i != m.end(); i++)if (i->second < k)//遍历，看看每种字符数量是否符合题意return 0;return 1;}
};这题难点在于思想，没有只用一次遍历得出答案，而是多次。
