【C/C++算法】从浅到深学习---滑动窗口（图文兼备 + 源码详解）

绪论：冲击蓝桥杯一起加油！！

每日激励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry”

绪论​：
本章是算法训练的第二章----滑动窗口，它的本质是双指针算法的衍生所以我将他们放到了连续的篇章，若看完双指针算法再来看本章会相对来说轻松点（传送阵）,后续还将继续持续更新算法（三天一更），直到蓝桥杯结束，敬请期待~
————————
早关注不迷路，话不多说安全带系好，发车啦（建议电脑观看）。

---

滑动窗口

本质其实是使用双指针暴力解法，控制移动指针下标的方式得到一片区间，类似像一个窗口，并且这个双指针在移动过程中若从分析题目得知其单调性让指针始终从左往右的移动，那么该双指针所指向的区间就是滑动窗口！

记住：
滑动窗口就是暴力双指针解法衍生出来的，一般分析出left、right指针都是一直往右移的那么就表示为滑动窗口

在解题时若见：连续子数组（子串），一般都可以尝试用滑动窗口算法

滑动窗口具体怎么用

最基本模板

1. left = 0，right = 0
2. 进窗口（维护窗口的信息）
3. 判断（根据窗口 信息判断 是否出窗口，可能为循环一次出多个窗口）1. 出窗口更新结果（位置不固定！）
根据题目放到合适的位置（这个多练几道题就能很轻松的掌握了）

如下图：

正确性：因为是利用单调性分析得出的他们同时像右移并且不用向左移动，规避了很多没必要的枚举行为，所以本质是分析出来的，就题论题！

时间复杂度：双指针始终都是往右移的，最大情况：n + n = 2n = O(N)

具体训练：

1. 长度最小的子数组

题目：

分析题目并提出，解决方法：

暴力解法：将所有子数组遍历出来，当遍历到一个区间后计算结果（如下图）

但这样遍历（时间复杂度：N²）* 计算结果（N）（就会导致时间复杂度非常大O(N³)，记住：像这种不断增加的线性区间，可以提前将每个区间的值算出来，然后存储在数组中（前缀和但此处仅仅浅浅的用了下，后面就会更新详细前缀和算法！），这样对计算结果的过程就能被优化为常数时间复杂度）

具体优化方法如下：
先遍历一遍，为了计算区间的值：

使用sum记录 left ~ right 区间的值，right每走一步就加上一步的值

并且我们遍历的过程，也不是无脑的遍历==，而是当结果一定不可是后面区间后，那么就直接跳过不算了（如下）==

而此时发现：right不用再移动回来了（因为在移动虽然满足条件但len长度一定会增大）
从而可以让left移动一步继续遍历其他区间

• 因为这段区间的值可以快速的算出来只需要sum - left位置的值即可
• 所以也得知他其实就是滑动窗口
  
  最终我们就能通过滑动窗口的基本模板来遍历这个数组，最终得到如下图滑动窗口移动过程：
  
  直到最后right移动到最后：
  

为何滑动窗⼝可以解决问题，并且时间复杂度更低？

• 这个窗⼝寻找的是：以当前窗⼝最左侧元素（记为 left1 ）为基准，符合条件的情况。也 就是在这道题中，从 left1 开始，满⾜区间和 sum >= target 时的最右侧（记为right1 ）能到哪⾥。
• 我们既然已经找到从 left1 开始的最优的区间，那么就可以⼤胆舍去 left1 。但是如 果继续像⽅法⼀⼀样，重新开始统计第⼆个元素（ left2 ）往后的和，势必会有⼤量重复 的计算（因为我们在求第⼀段区间的时候，已经算出很多元素的和了，这些和是可以在计算 下次区间和的时候⽤上的）。
• 此时， rigth1 的作⽤就体现出来了，我们只需将 left1 这个值从 sum 中剔除。从right1 这个元素开始，往后找满⾜ left2 元素的区间（此时 right1 也有可能是满 ⾜的，因为 left1 可能很⼩。 sum 剔除掉 left1 之后，依旧满⾜⼤于等于target ）。这样我们就能省掉⼤量重复的计算。
• 这样我们不仅能解决问题，⽽且效率也会⼤⼤提升。 时间复杂度：虽然代码是两层循环，但是我们的 left 指针和 right 指针都是不回退的，两者 最多都往后移动 n 次。因此时间复杂度是 O(N)。

题解核心逻辑（源码）：

诸多细节已注释到代码中（见下）：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {// 通过暴力解法，分析题目可知我们可以使用滑动窗口，也就是left right双指针都只需要往右移，不用恢复回来（向左移）int sum = 0,res = INT_MAX;//循环for(int left = 0,right = 0;right < nums.size();right++){//进窗口://本质就是将right下标指向的值，添加到sum计数器中sum +=  nums[right];//并且right向后移动 ++//判断://一般来说都是判断是否需要出窗口，本题也就是判断，sum 是否大于 target，若大于了就需要出窗口了//该判断也是一定要按题意来的，本题对于大于等于target的值后就不再需要往后遍历了，所以就出窗口//所以我们需要知道什么时候出窗口，它的具体条件是什么！while(sum >= target){//记录答案://记录答案一般来说就是最大或最小值//一般来说都是查看当前区间的值 是否满足最大或者最小，若满足就保存否则跳过//本题是找最小的长度，所以说我们需要判断该区间是否最小res = min(res,right - left + 1);//出窗口：//就比较简单一般来说就是将left上的值从当前区间，sum计数器中减去//本质：也就是记录之前的值，然后要更新成新的值了//减去left的值，并让left移动，形成新的区间sum -= nums[left];left++;}}return res == INT_MAX ? 0 : res;}
};

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

题目：

分析题目并提出，解决方法：

通过上图就能很快的认知到题目的目的：
找到一个最长不包含重复字符的字串

暴力解法很好想：遍历呗，遍历所有情况最终记录最短的即可，但能不能优化呢？

其中不难发现条件中的不能出现重复，那么在我们遍历的过程中，若出现了重复的是不是就可以把之前的记录了，然后再舍弃最后得到新满足的区间，在继续往后记录查找。

那如何快速的判断是否出现重复字符呢？

hash表！，通过在遍历的过程中，通过hash表记录遍历过的字符，当hash中对应字符的值大于1后就表示出现了重复！！

题解核心逻辑：

当区间出现重复字符的时候left就需要往移，但只移动一步的话，很明显right肯定还将碰到重复的值（对于上图来说），所以说我们需要将left移动到重复值的下一个位置：

right不用回来继续往右移即可，因为left就是将重复的给跳过了，所以区间中一定不会出现重复的了
那么到此就发现它又是一个：滑动窗口！

那么就结合滑动窗口的基本模板，就本题分析修改判断以及进窗口出窗口该怎么写！
分析得出：

class Solution {
public:int lengthOfLongestSubstring(string s) {if(s.size() == 0) return 0;int hash[128] = {0};int res = INT_MIN;for(int left = 0,right = 0;right < s.size() ; right++){//进窗口hash[s[right]]++;//针对s[right]字符进窗口//判断，若出现重复字符while(hash[s[right]]>1){//出窗口hash[s[left]]--;left++;}//每次都记录，这次不再内部记录，是因为进去后是出现了重复了字符了，记录的长度就不对了//他不想上一题有冗余度：大于等于target都行res = max(res,right - left + 1);}return res;}
};

3. 最大连续1的个数 III

题目：

分析题目并提出，解决方法：

分析暴力解法：

1. 可以用双指针来确定连续的1的区间，然后对于可翻转0通过记录个数zero
2. 当zero个数大于k后，代表区间不满足条件了，right就不能移动，需要移动left。
3. 再重新遍历所有新区间，最终得到所有情况。

具体如下图：

当正常枚举时zero的个数为k后，则right就不能再继续往后了，该left移动了

优化：
而left若只移动一步则left ~ right 区间内 的zero还是等于k（如上图），那么长度肯定不会增加，right就没有必要重新回来枚举。

所以left一个不断移动直到让 left ~ right 区间内zero不等于k

再继续移动right，此处就有可知left right都是一直往右移动，所以可以使用滑动窗口

题解核心逻辑：

最终得出滑动窗口模板分析（如下图：）

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int zero = 0,res = 0;for(int left = 0,right = 0; right < nums.size();right++){//进窗口if(nums[right] == 0){zero++;}//判断，当0的个数大于了k，表示子数组不符合条件了while(zero > k){//出窗口if(nums[left] == 0){zero--;}left++;}res = max(res,right - left + 1);}return res;}
};

4. 将 x 减到 0 的最小操作数

题目：

分析题目并提出，解决方法：

题目要求找到从左右最少次数删除得到0

但若直接从正面想，每次左右删除可能性非常多，非常难写（到底先左还是先右）

此时我们可以反过来思考下：

正难则反

既然想两边比较困难，那么在线性中，选择了两左右两边，那么中间就是单独出来的！

那么就转换成了找 最长、子数组 的长度，所有元素的和正好等于target（sum - x）

不难发现它和我们之前做的第一题相反（1. 长度最小的子数组）

题解核心逻辑：

那么就可以尝试用双指针遍历所有区间查找
当left ~ right 区间大小大于等于target

此时right不用再移动了，因为需要找的事刚好等于target，在移动只会更大
所以需要移动left：

但移动left后，right不需要再回来重新遍历，因为只会更小
所以right和left都是始终向右移动的，也就是滑动窗口

class Solution {
public:int minOperations(vector<int>& nums, int x) {//分析得知使用滑动窗口找到值为 target (nums所有值 - x) d 最大连续子数组int target = accumulate(nums.begin(),nums.end(),0) - x;int n = nums.size();if(target < 0) return -1;int sum = 0,len = -1;for(int left = 0,right = 0;right < n;right++){//进窗口sum += nums[right];//sum存储值，找值为target的最大连续子数组//判断：while(sum > target){//出窗口sum -= nums[left];if(left < n){left++;}}//记录结果，找到值为target就记录一下if(sum == target){len = max(len,right - left + 1);}}if(len == -1){return -1;}return  n - len;}
};

5. 水果成篮

题目：

分析题目并提出，解决方法：

分析题目，可知题目所需为：在数组中找到最长的子数组，并且水果类型不超过两种，就很有滑动窗口的特性，所以我们直接上滑动窗口

题解核心逻辑：

使用双指针

当left右移后：水果类型kinds的变化

不难发现right没有必要回来到left位置重新（左移）遍历，而事等待水果个数变小（left移动）后再继续右移

所以：left、right都是始终保持右移的，也就是滑动窗口！
算法原理：

class Solution {
public:int totalFruit(vector<int>& fruits) {int kinds = 0;//记录水果类型个数int hash[100010] ={ 0};//记录水果出现次数int res = 0;//结果//最终要找的是最大的子数组长度for(int left = 0,right = 0;right < fruits.size();right++){//进窗口。水果的个数小于2时if(kinds <= 2){if(hash[fruits[right]] == 0){kinds++;//如果水果没有出现过 类型就要++}hash[fruits[right]]++;}//当水果类型超过2种的时候就要出窗口了while(kinds > 2){hash[fruits[left]]--;if(hash[fruits[left]] == 0){kinds--;}left++;}res = max(res,right - left + 1);}return res;}
};

6. 找到字符串中所有字母异位词

题目：

分析题目并提出，解决方法：

分析题目可知本题题意为：

判断两个字符串是否是异位词（字符相同可能顺序不同）：

直接通过两个hash表，存储着他们各自字符的个数，然后比较这些个数是否相同即可知道字符串是否相同，若个数相同则代表元素相同只不过顺序不同！

题解核心逻辑：

这样我们就能得知方法：
暴力解法：

1. 先获取目标字符串个数
2. 使用双指针指向该相同个数的字符串区间
3. 移动遍历，比较一下和目标字符串中的元素个数是否都相同
4. 其中不难看出来left ~ right区间中right其实不需要回来，因为长度是固定的，所以该区间只需要不断往前，也就是left、right不断++，最终就能遍历所有区间。
   
   所以因为left、right不断++，所以也就是滑动窗口：
   

class Solution {
public:bool Check(int hash1[26],int hash2[26]){for(int i = 0;i < 26;i++){if(hash1[i] != hash2[i]){return false;}}return true;}vector<int> findAnagrams(string s, string p) {int hash1[26] = {0};//存储滑动窗口中元素的个数int hash2[26] = {0};//存储目标个数for(auto c : p){hash2[c-'a']++;}vector<int> res;for(int left = 0,right = 0;right < s.size(); right++){//进窗口hash1[s[right] - 'a']++;if(right - left + 1 > p.size()){hash1[s[left] - 'a']--; left++;}if(Check(hash1,hash2)){res.push_back(left);}}return res;}
};

其中对于Check检查字符串是否为异位词函数来说，本质也还是遍历两个数组26次，虽然微不足道，但还能优化，具体如下：

其中使用count记录有效字符个数，何为有效？

1. 在滑动窗口滑动的过程中，窗口内的元素决定了有效字符个数
2. 有效字符：
   1. 根据题意要找的是对应字符串中的相同字符
   2. 那么在滑动窗口中
   3. 进窗口：
   4. 若进窗口的字符和对应字符串中的某个字符相等（字符相等）
   5. 且窗口内的已有个数小于等于对应窗口中的个数（个数小于等于）
   6. 有效的，count++
   7. 反之不有效count不变
   8. 出窗口：
   9. 同样也需要判断出窗口的字符是否是有效字符
   10. 若是则需要修改count–
   11. 当count == 对应字符串中的个数，即代表刚好找到了，那么就更新结果
3. 总结就是使用一个count有效字符计数器来判断是否找到了

优化后代码：

class Solution {
public:vector<int> findAnagrams(string s, string p) {int hash1[26] = {0};//存储滑动窗口中元素的个数int hash2[26] = {0};//存储目标个数int count = 0;for(auto c : p) hash2[c-'a']++;vector<int> res;for(int left = 0,right = 0;right < s.size(); right++){//进窗口hash1[s[right] - 'a']++;if(hash1[s[right] - 'a'] <= hash2[s[right] - 'a']){count++;}if(right - left + 1 > p.size()){if(hash1[s[left] - 'a'] <= hash2[s[left] - 'a']){count--;}hash1[s[left] - 'a']--;left++;}if(count == p.size()){res.push_back(left);}}return res;}
};

7. 串联所有单词的子串

题目：

分析题目并提出，解决方法：

分析题目画出下图：
理解题目所需：从s中找到w字符串数组的不同排列情况
如下图：w : “foo”、“bar”
那么s中符合条件的如下画横线处：

通过图像我们不难看出假设，把s和w中的字符串以其s内部的字符串长度为划分看出一个个字符：
那么就将变成如下图形式：

那么本题就很前面走的一题非常相似：找异位词！
所以使用同样的方法，只不过此时left和right的移动需要改变从w中字符串长度

其中注意的是：
要遍历所有情况，也就是改变left的起始位置 [ 0 ~ len），这样才能遍历所有情况，具体如下不同颜色的横线

题解核心逻辑：

核心逻辑和找异位词一致：
不同的是：

1. left和right的移动长度需要修改
2. 比较时通过hash存储字符比较相同
3. 在最外层增加一个循环顾忌所有情况

更多细节见源码：

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {//分析可知本题和字母异位词很像，类似：将字符串看成字符vector<int> res;unordered_map<string,int> hash2;//存储words中个数int n_hash2 = 0;for(auto& s : words){n_hash2++;hash2[s]++;}int len = words[0].size();for(int i = 0 ; i < len; i++){//注意 hash1 、 count 需要放到内部，初始化，防止下一次遍历使用到上次的数据unordered_map<string,int> hash1;//存储个数int count = 0;//同样使用 有效字符记录for(int left = i,right = i;right < s.size();right += len){string sub1 = s.substr(right,len);//进窗口hash1[sub1]++;// hash2.count(sub1) 避免   hash2[sub1] 内部数据不存在时的创建该数据的消耗if( hash2.count(sub1) &&  hash1[sub1] <= hash2[sub1]){count++;}//判断是否出窗口，窗口中的个数是否大于所找的字符串个数// 画图可知：((right - left) / len) + 1 为当前滑动窗口元素个数// n_hash2 为所找的字符串的元素个数if(((right - left) / len) + 1 >  n_hash2){string sub2 = s.substr(left,len);//if(hash2.count(sub2) && hash1[sub2] <= hash2[sub2]){count--;}hash1[sub2]--;//出窗口left += len;}if(count == n_hash2){res.push_back(left);}}}return res;}
};

8.最小覆盖子串

题目：

分析题目并提出，解决方法：

分析题目可知本题：从s字符串中找到最短的包含t字符串中所有字符的子串
如下图：ADOBEC（就包含了所有t：ABC）、BECODEBA（同样也包含所有）、BANC
其中不难看出BANC最短，所以他就是最终答案
具体如下图：

那么就能推出，暴力解法：使用双指针遍历所有区间，并且使用哈希表来判断是否已经包含t字符串了

但我们再暴力解法的情况下再分析，看看是否符合滑动窗口：

不难发现下面情况：

right没必要回去了，因为只有两种可能：

1. left 右移区间改变，但仍然符合条件，那么right移动回来，再往右找，最终还会移动到相同的为止停下来（因为条件没变，right指向的地方仍然是最后一个值）
2. 若left右移区间改变，但不符合条件了，那么right肯定会移动到原来位置再往右的位置才可能停下

题解核心逻辑：

那么就是滑动窗口了：
分析题意的下面滑动窗口模板：

优化：
同样是使用一个count进行记录有效字符个数，代替使用hash表的比较记录，但本题中他的条件不要一样，并不需要找到异位词，而是找到包含t中所有字符的即可，而其中相同的字符可能会出现多次，所以count只有在 滑动窗口中某个元素的个数 = 目标字符串的某个元素的个数时才++和–，因为假如 count 是 >= 目标个数（肯定不是小于，小于不符合个数大于等于条件）时都 ++ 的话那么可能会多算

记住count是有效字符个数，我们要结合好题目所给的条件进行设置！（此题见题目中的注意事项可知：“不少于”）

class Solution {
public:string minWindow(string s, string t) {unordered_map<char,int> hash1;//存储滑动窗口内部数据unordered_map<char,int> hash2;//存储t字符中的元素for(auto c : t) hash2[c]++;int count = 0;//维护一个有效字符个数计数器i、nt len = INT_MAX;//用于比较长度，找到最小的长度int l_res = -1;for(int left = 0,right = 0; right < s.size() ;right++){//进窗口hash1[s[right]]++;//hash2.count(s[right])这里是防止hash2[s[right]]创建新的字符if(hash2.count(s[right]) && hash1[s[right]] == hash2[s[right]]) count++;//判断while(count == hash2.size()){//记录if(right - left + 1 < len){len = right - left + 1;l_res = left;}//出窗口if(hash2.count(s[left]) && hash1[s[left]] == hash2[s[left]]) count--;hash1[s[left]]--;left++;}}if(l_res == -1) return "";return s.substr(l_res,len);}
};不使用容器：
class Solution {
public:string minWindow(string s, string t) {int hash1[128]  = {0};//存储滑动窗口内部数据int hash2[128]  = {0};//存储t字符中的元素int kinds = 0;for(auto c : t) {if(hash2[c] == 0) kinds++;//若果为0代表新类型hash2[c]++;}int count = 0;//维护一个有效字符个数计数器int len = INT_MAX,begin = -1;//len记录最小的长度、begin记录最小长度的起始位置for(int left = 0,right = 0; right < s.size() ;right++){//进窗口hash1[s[right]]++;if(hash1[s[right]] == hash2[s[right]]) count++;//判断while(count == kinds){//记录，找到新的小的长度if(right - left + 1 < len){len = right - left + 1;begin = left;}//出窗口if(hash1[s[left]] == hash2[s[left]]) count--;hash1[s[left]]--;left++;}}if(begin == -1) return "";return s.substr(begin,len);}
};