利用滑动窗口解题

前言：

第一题：209. 长度最小的子数组 - 力扣（LeetCode）

第二题：1004. 最大连续1的个数 III - 力扣（LeetCode）

第三题：3. 无重复字符的最长子串 - 力扣（LeetCode）

第四题：1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

第五题：904. 水果成篮 - 力扣（LeetCode）

第六题：30. 串联所有单词的子串 - 力扣（LeetCode）

第七题： 438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

第八题：76. 最小覆盖子串 - 力扣（LeetCode）

总结：

前言：

本篇文章还是以先介绍题目意思，然后再解释以下算法原理，最后再是给出代码的实现。

但是与上篇文章不同的是，这篇文章回给出为什么要用滑动窗口解题，怎么想到的，以及滑动窗口的原理到底是什么。所以前两题会以最详细的方法进行说明，会先从暴力解法出发，进行一步一步的优化，从而到达其代码与滑动窗口类似，从而达到解释为什么用滑动窗口解题。

第一题：209. 长度最小的子数组 - 力扣（LeetCode）

题目解释：

题目的意思很好理解，但是需要注意的是这里的子数组是一个连续的子数组，意思是：你只能挑选下标连续的元素，不能挑选不连续的，比如：下标0，下标2......他就不连续，所以不是子数组。

为什么要这样写？为什么要用滑动窗口？ 下面以题目中的示例一为例说明。

对于一个题，看完题首先去想的应该不是最优算法，而是怎么使用暴力解法去写，然而对于这道题的暴力写法也很好写，我们只需遍历数组长度的次数（设为Len）。在每一趟中，从起始位置i开始，我们将遍历整个数组，并计算出当前的和sun。如果sun大于一个预定值sum，则更新结果，并结束本趟遍历。时间复杂度为0（n^2）

就拿示例一，我们先模拟第一趟

所以我们进行优化，对于每趟的遍历，如果第一次出现sum>=target的情况，则结束本趟的遍历，虽然从时间复杂度上没有太大变化，但还是优化了不少的时间的。

第一次优化完后，你肯定是很疑惑的，力扣中等题不可能这么简单吧，对，就是不这么简单，你把优化过后的代码提交，发现是过不了的，是超时的。所以我们还需要再进行优化。

我们发现没遍历一趟结束后，都需要进行sum=0，对sum进行刷新，然后再依次向后遍历到上次结束的位置。

所以再优化暴力解法，将sum=0，去掉，然后每一趟遍历结束后，先更行结果，然后再减去左边的元素。

本次优化的结果需要将原本的暴力解法代码大致完全修改，代码写完后此时提交是可以过的。

虽然这种算法思路是我自己想出来的，并没有遵循特定的算法框架。在用暴力完成这个题目后，成就感是很高的，但其实我们并不知道这是一种什么样的算法，你对于你想出来的这个思路总的掌握来说还是不牢固的。实际上，这种思路就是滑动窗口算法。

那么下面就用本题说明下滑动窗口的算法

算法原理：

我们上面对暴力解法的优化都是对一个数组进行的操作，其操作空间类似一个可以滑动的小窗口，所以该算法就叫滑动窗口

滑动：说明窗口不是固定不变的，而是具有一定的可变性的

窗口：窗口并不是一定固定不变的，可以进行扩大，然后逐步进行缩小直到满足情况

其大致操作可以分为三步

初始化left，right
进窗口
判断条件（一般是刚好超出题目的符合要求的边界），出窗口，是否更新结果（出窗口与判断不分先后，不同题目先后不同，根据题目分析定先后）需要注意的是可能出一个还是满足出窗口的条件，有时要用while循环出窗口，又是只是if出一次

注意不同的题目对于步骤三也会不同，可能把更新结果变为第四步，而不是放在循环里面

那么为了详细一点就那示例一模拟一下

while循环的结束条件就为right>=n。

首先就先判断，更新结果与出窗口相对位置，需要注意的是对于本题，可能出一个还是满足出窗口的条件，所以要用while循环出窗口，判断条件就为sum>=target，换句话说，就是如果当前维护的窗口的合为8，如果左边界为1，左边界出窗口后如果合依旧大于target，那么就需要再进行出窗口操作。

下面给出图解，我们省略前几步进窗口的操作，从第一次判断开始模拟

给出模拟以后大致思路就很清楚了

用小图画出思路就为：

代码实现：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left=0,right=0;int n=nums.size();if (n == 0) {return 0;}int sum=0;int ret=INT_MAX;while(right<n){while(right<n && sum<target){sum+=nums[right];right++;}while(left<right && sum>=target){ret=min(ret,right-left);sum-=nums[left];left++;}}return ret==INT_MAX? 0 : ret;}
};

第二题：1004. 最大连续1的个数 III - 力扣（LeetCode）

题目解释：

题目也没什么好解释的，但要注意你不是一定要翻转k个0才更行结果，就比如说如果给出一个案例k=2，然后数组中只有一个0，那么反转1个然后统计所有的1，也可以作为返回值返回。

同样，我们先从暴力解法开始

暴力枚举+zero计数器

依旧分两层循环，再利用双指针。暴力枚举出所有反转k个0，统计该数组的个数。

同样跟第一题一样可以优化，在每一次遍历完成后，我们需要将右边界更新为左边界，然后继续向右移动。然而，这样的操作意味着我们会经过上一次遍历结束时的位置，从而导致重复计算。为了避免这种冗余操作，我们可以对算法进行优化。

经过这一步优化，其大致思路就与滑动窗口有点相似了，如果看完第一个讲解，那么应该很容易反应过来应该使用滑动窗口

所以我们拿出来滑动窗口的三步骤

我们这时候需要解决的问题就为，是先出窗口还是先更新结果。还是说更新结果放在别处，

经过思考，如果想要出窗口，那么此时的count计数器肯定是大于k的，肯定是已经翻转个数超过k，如果再循环里面更新，那么可能导致第一个出的本来就是1，所以更新要放到循环外，定为第四步。

那么对于每一步，我们再分析详细操作

对于进窗口，不变的就是进完有right++，但是如果进的是1，则无操作，如果是0则，计数器++

判断条件就为zero>k时，但要用while循环

代码实现：

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n=nums.size();int ret=0;for(int right=0,left=0,zero=0;right<n;right++){if(nums[right]==0) zero++;while(zero>k){if(nums[left++] == 0) zero--;}ret=max(ret,right-left+1);}return ret;}
};

第三题：3. 无重复字符的最长子串 - 力扣（LeetCode）

题目也是很好读懂的也不需要解释

看完前两个的题目解释，那么对于本题就不在从暴力算法优化到与滑动窗口差不多思路的步骤了，

直接从滑动窗口解题

思路：

如何想到用滑动窗口 本段摘自力扣官方题解

那么如此一来就可以使用滑动窗口来解此题了

代码实现：

同样，我们拿出滑动窗口的三步图，我们先解决出窗口与更新条件的位置关系，同样，跟第二题一样，如果再循环里面更新，那么导致第一个出后该窗口内还是存在重复的字符，所以更新要放到循环外，定为第四步。

对于进窗口就是一成不变的将其添加到窗口内。但是这里就需要考虑那么出窗口的条件呢？

需要判断是否出现重复的，跟前两题不一样了，前两题只需要根据窗口的个数或者计数器的大小，但是这如果你还去遍历窗口的话那时间复杂度要高了，还不如用暴力呢。

所以我们就需要用哈希表或者创建一个数组，其大小为26，对应着26个字母，本题就用哈希表了。

所以把上面的想清后，我们把每一步详细一下，就变为了下面：

代码实现：

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_set<char> occ;int n=s.size();if(n==0){return 0;}int ret=-1,r=-1;for(int i=0;i<n;i++){if(i!=0){occ.erase(s[i-1]);}while(r+1<n && !occ.count(s[r+1])){occ.insert(s[r+1]);++r;}ret=max(ret,r-i+1);}return ret;}
};

第四题：1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

其实对于本道题，如果不明确告诉你用滑动窗口解题，那么这道题其实非常难写的。

但是换句话说，如果明确告诉你用滑动窗口去写，你能反应过来怎么去写么？

我一开始也没反应过来如何去写，也是听了听别人给的一点思路，然后想了想，才写出来的。

其实这道题正着想很难，但是如果反着想，我们把这道题改为计算合为sum-x的最大连续子数组，但返回值为n-最长连续子数组的大小。那么就很好解决了

依旧拿出滑动窗口三小步

先判断更新结果与出窗口的位置关系：更新结果在出窗口循环的外面

我们进窗口就是tmp+=nums[right];

判断条件就为：(tmp>target)

出窗口：tmp-=nums[left++];

更新条件就为：if(tmp==target) ret=max(ret,right-left+1);

对图中的每一步完善：

代码实现：

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum=0;for(auto& num:nums) sum+=num;if(sum<x) return -1;int target=sum-x;int left=0,right=0;int n=nums.size();int tmp=0;int ret=-1;for(;right<n;right++){tmp+=nums[right];while(tmp>target){tmp-=nums[left++];}if(tmp==target){ret=max(ret,right-left+1);}}return ret==-1?-1:n-ret;}
};

第五题：904. 水果成篮 - 力扣（LeetCode）

题目解释：

这一道题读下来就很蒙了，根本不知道在说什么。

如果用一句话概括就是：找至多包含两种元素的最长子串（连续），返回其长度。

如果英文直译就是：您正在参观一个农场，该农场有一排从左到右排列的果树。树由整数数组fruits表示，其中水果[i]是第i棵树产生的水果类型。你想收集尽可能多的水果。但是，所有者有一些严格的规则，您必须遵守：你只有两个篮子，每个篮子只能装一种水果。每篮水果的数量没有限制。从您选择的任何一棵树开始，您必须在向右移动时从每棵树（包括起始树）中恰好摘下一个水果,摘下的水果必须放在你的一个篮子里。一旦你到了一棵树上，树上的果实没法放入你的篮子（两个篮子已经满了），你必须停下来。给定整数数组水果，返回可以拾取的最大水果数。本题，其实就是选只有两个元素的最长连续子序列，比如1，2，3，2，2最长就是2，3，2，2（只包括2或者3，而且是最长的）。

算法原理：

那么这道题就很好解决了，用滑动窗口来写，难度甚至可以说是简单题，但是我们需要解决的一点就是如何判断添加下一个元素后，使得包含的元素种类超过2.

对于这个问题，第一时间想到的应该时引用哈希表。

这里就不在按照滑动窗口的三小步来写了，直接给出用哈希与滑动窗口的代码了

class Solution {
public:int totalFruit(vector<int>& fruits) {int ret=0;int n=fruits.size();unordered_map<int,int> mp;for(int left=0,right=0,count=0;right<n;right++){//进窗口mp[fruits[right]]++;count++;//判断 出窗口while(mp.size()>2){mp[fruits[left]]--;if(mp[fruits[left]]==0){mp.erase(fruits[left]);}left++;count--;}ret=max(ret,count);}return ret;}
};

但是这样提交代码后

所以我们来说一下优化

我们知道哈希表的删除的时间复杂度时0（n）的，所以对于时间的优化就是对与哈希表的优化，能否不用删除呢？如果说不用删除的话，那么对于判断条件就不能用mp.size()>2了，就需要用迭代器遍历，统计哈希表的长度了，我们修改一下，看看时间消耗

代码：

class Solution {
public:int totalFruit(std::vector<int>& fruits) {int ret = 0;int n = fruits.size();std::unordered_map<int, int> mp;  // 存储水果种类及其数量int left = 0;  // 滑动窗口的左边界for (int right = 0; right < n; ++right) {// 进窗口，增加当前右指针所指水果的数量mp[fruits[right]]++;// 判断是否超过两种水果，如果超过，则开始收缩窗口while (countUniqueFruits(mp) > 2) {// 移动左指针，减少左指向水果的数量mp[fruits[left]]--;left++;  // 收缩窗口}// 更新最大窗口大小ret = std::max(ret, right - left + 1);}return ret;}private:// 辅助函数：计算当前窗口内不同水果的种类数int countUniqueFruits(const std::unordered_map<int, int>& mp) {int uniqueCount = 0;for (const auto& entry : mp) {if (entry.second > 0) {uniqueCount++;}}return uniqueCount;}
};

但是运行提交发现：

所以说我们还是要另辟蹊径，要舍去用哈希表，我们不妨使用vector来维护

class Solution {
public:int totalFruit(vector<int>& fruits) {int left = 0;vector<int> intCounts(fruits.size());//记录某种水果采摘的个数int kinds = 0;//记录采摘水果的种类int ans = 0;for(int i=0;i<fruits.size();i++){if(intCounts[fruits[i]] == 0){kinds++;}intCounts[fruits[i]]++;while(kinds >2){//发现采摘种类大于2时，left开始右移intCounts[fruits[left]]--;//每次右移都丢掉对应篮子里的水果if(intCounts[fruits[left]] == 0){ // 直到把某个篮子里的水果丢空则种类-1.kinds--;}left++;}ans = max(ans,i-left+1);}return ans;}
};

这样就好多了

第六题：30. 串联所有单词的子串 - 力扣（LeetCode）

对于这道题不要看到是困难就怕了，看到题目这么长就不想看了，其实用滑动窗口来写，其实不是那么的难。只需要把细节处理好久简单多了。

只是相对于上面的等题是对单个字符进行操作，这里的操作变为了对一个小的字符串进行操作

其实本质还是一样的。

那么这里就给出不一样的区别，right指针像前面都是移动长度为1，这里变为了len（len为words里面每个字符串的长度），哈希表的键值对存的是<string，int>，而不是像前面几个题一样存的是<int,int>或者<char,int>。

基本变量设置：
- len：每个单词的长度。
- n：字符串 s 的长度。
- m：单词数组 words 中单词的数量。
- hash1：记录 words 中每个单词的出现次数，作为参考标准。
外层循环
- i 代表当前尝试的起始位置，外层循环的目的是为了从字符串 s 中不同的起始位置开始尝试。因为每个单词的长度是固定的，因此从 0 到 len-1 的不同起始位置可以保证覆盖所有可能的排列。

这种写法仅实现了单层循环，确保了从首个字符开始逐个遍历检查该单词是否存在于words中。这意味着，尽管第1、2、3个字符的组合恰好存在于words中，但第0、1、2个字符的组合却并不存在。所以我们还需要设置外层循环，循环len次

滑动窗口：
- 内层循环使用 left 和 right 来标记滑动窗口的左右边界。
- right 每次增加 len，即窗口向右扩展一个单词的长度。
- left 是窗口的左边界，只有当窗口的总长度大于 len * m 时，left 才会向右移动（收缩窗口）。
哈希表：
- hash2：记录当前窗口内每个单词出现的次数。
- 当 right 指针扩展时，hash2 增加当前单词的计数。如果该单词出现的次数小于等于 words 中该单词的频次 (hash1)，count 就会增加。
窗口收缩：
- 当窗口大小超过 len * m（即包含了超过 m 个单词的长度），需要收缩窗口。通过移动 left 来收缩窗口，直到窗口中只包含 m 个单词。
- 收缩时，left 向右移动，移出窗口的单词会从 hash2 中减去计数，如果该单词的计数为 0，则直接从 hash2 中删除该单词。
判断合法窗口：
- 如果窗口内的单词数量等于 m（即当前窗口包含了 words 中的所有单词），就记录下 left 作为有效的子串起始位置。

那么根据思路写出代码

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> v;int len = words[0].size();int n = s.size();int m = words.size();unordered_map<string, int> hash1;for (auto& word : words) hash1[word]++;for (int i = 0; i < len; i++){unordered_map<string, int> hash2;for (int left = i, right = i, count = 0; right < n; right += len){// 进窗口string in = s.substr(right, len);hash2[in]++;if (hash2[in] <= hash1[in]) count++;//判断出if (right - left + 1 > len * m){string out = s.substr(left, len);if (hash2[out] <= hash1[out]) count--;hash2[out]--;if (hash2[out] == 0){hash2.erase(out);}left += len;}if (count == m){v.push_back(left);}}}return v;}
};

提交发现，效果不是很佳，所以我们就要进行必要的优化，对于哈希表的删除是一个0（n）的时间复杂度，所以我们要尽可能避免进行删除，

我看了看别人的思路，然后结合了一下，对代码进行了修改

修改地方如下：

如果要进窗口的字符串在words内不存在，那么就进行伪插入到hash2，这样，如果在出窗口是，如果要出窗口的字符串本就不在words内，那就根本就不需要进行删除或者hash2的second--，如果在，那么只进行--，如果--到0，也没关系，因为我们还定义了另一个变量计数器count统计其符合的字符串数量。

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> v;int len = words[0].size();int n = s.size();int m = words.size();if (n < len * m) return v; // 长度不够的情况unordered_map<string, int> hash1; // 记录每个单词出现的次数for (const auto& word : words) hash1[word]++;// 外层循环：从 0 到 len-1，每次从不同位置开始for (int i = 0; i < len; i++) {unordered_map<string, int> hash2; // 记录当前窗口中单词出现的次数int left = i, right = i, count = 0;while (right + len <= n) {// 进窗口string in = s.substr(right, len);right += len;if (hash1.find(in) != hash1.end()) {hash2[in]++;if (hash2[in] <= hash1[in]) {count++;}}// 判断出窗口，收缩窗口while (right - left > len * m) {string out = s.substr(left, len);left += len;if (hash1.find(out) != hash1.end()) {if (hash2[out] <= hash1[out]) {count--;}hash2[out]--; // 直接减少，不调用 erase}}// 如果窗口内包含了所有单词if (count == m) {v.push_back(left);}}}return v;}
};

这样，无论时间上还是空间上，都得到了很大的优化

第七题： 438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

需要解释的就是何为字母异位词

比如示例一的cba，bac都是abc异位词。

初始化字符频率：
- hash1 数组用于存储字符串 p 中每个字母的频率（大小为26，因为只有小写字母）。
- hash2 数组用于存储当前滑动窗口内的字符频率。
滑动窗口：
- 使用两个指针 left 和 right 来表示滑动窗口的范围，right 用于扩展窗口，left 用于收缩窗口。
- count 变量用于记录当前窗口中已匹配的字符数。
窗口扩展：
- 每次移动 right 指针时，增加 right 指向字符的频率计数 (hash2)。
- 如果当前字符在 s 中的计数不超过在 p 中的计数，count 变量增加，表示当前字符已经符合要求。
窗口收缩：
- 如果窗口的大小超过了 p 的长度 m（即 right - left + 1 > m），则需要通过移动 left 指针来缩小窗口，并更新 hash2 中相应字符的计数。
- 如果移除的字符的计数仍然不超过 p 中相应字符的计数，则 count 减少。
匹配检测：
- 每当 count 等于 m 时，说明当前窗口中的字符频率与 p 完全匹配，此时记录当前窗口的左边界 left 作为一个有效的起始索引。
返回结果：
- 最终，所有符合条件的起始位置会被存入 ret 向量，并返回。

class Solution {
public:vector<int> findAnagrams(string s, string p) {int hash1[26]={0};int m=p.size();for(auto& e:p) hash1[e-'a']++;int hash2[26]={0};int n=s.size();vector<int> ret;for(int left=0,right=0,count=0;right<n;right++){char in=s[right];//进窗口hash2[in-'a']++;if(hash2[in-'a']<=hash1[in-'a']) count++;//出窗口char ou=s[left];if(right-left+1>m ){if(hash2[ou-'a']--<=hash1[ou-'a']) count--;left++;}//更新结果if(count==m){ret.push_back(left);}}return ret;}
};

第八题：76. 最小覆盖子串 - 力扣（LeetCode）

题目解释：

对于本道题，读一遍便可以知道要做什么，那我要提醒的是：对于示例一，用黑色框起来的也算其结果之一，只是不是最优解，虽然他又两个B，但也是一种结果。

对于本道题其实根本谈不上困难

用滑动窗口来写，大致思路就是下面的图形思路，但是这里就不提倡用哈希表了，建议使用创建一个大小128的数组来维护。后面说为什么。

但是这样写完，换句话说在代码中的check就发现其实check其实非常耗时间的，因为我们要遍历哈希表，如果正好符合要求还好，如果迭代器遍历的时候是需要两个迭代器的，你要做到的就是要保证两个迭代器对应的first一致。这就很难保证。

所以就像上面说的建议用数组，然而用数组的话又要遍历128遍，虽然对于cpu128遍很快，但我们还是要进行优化的。

优化方式就是使用一个count计数器，统计符合要求的个数。

代码如下：

class Solution {
public:string minWindow(string s, string t) {int n=s.size();int hash1[128]={0};int kinds=0;for(auto& e:t){if(hash1[e]==0){kinds++;}hash1[e]++;}int mi=INT_MAX;int hash2[128]={0};int begin=-1;for(int left=0,right=0,count=0;right<n;right++){char in=s[right];if(++hash2[in]==hash1[in]) count++;while(count==kinds){if(right-left+1<mi){mi=right-left+1;begin=left;}char ou=s[left];if(hash2[ou]==hash1[ou]) count--;hash2[ou]--;left++;}}if(begin==-1) return "";else return s.substr(begin,mi);}
};

总结：

滑动窗口（Sliding Window）是一种在数组或字符串等线性数据结构上进行子数组（或子字符串）操作的技术，常用于处理具有 连续性 或 局部性质 的问题。总结来说，滑动窗口适用于以下几种情境：

1. 子数组/子串的所有情况需要遍历

当问题要求你遍历某个子数组或子串的所有可能的连续部分时，滑动窗口是一种非常高效的解法。通过动态调整窗口的大小或位置，你可以避免重复计算，从而提高效率。

2. 需要计算某些连续元素的属性（如和、最大值、最小值、频率等）

典型的滑动窗口问题包括计算连续子数组的和、最大最小值、平均值、字符出现的频率等。
例子：给定一个整数数组 nums，你需要计算所有大小为 k 的子数组的和。使用滑动窗口可以避免重新计算每个子数组的和，从而降低时间复杂度。

3. 找到满足某些条件的最短或最长子数组

当需要找到满足某些条件（如和、乘积、满足某种限制）的最短或最长的子数组时，滑动窗口特别有用。通过动态调整窗口的左右边界，可以逐渐扩大或收缩窗口，以满足问题的需求。
例子：给定一个字符串，你需要找到包含所有字母异位词的最短子串。

4. 当问题可以通过增量或递减计算的方式优化

滑动窗口的一个关键优势是当窗口扩展或收缩时，能够增量式地更新结果，避免重新计算整个子数组或子串的结果。
例子：在求解字符串中的某些字符的频率或和时，滑动窗口允许你快速更新窗口边界，而不需要每次都重新计算全部内容。

5. 有固定大小的窗口或可变大小的窗口

滑动窗口有两种常见变体：
- 固定大小的窗口：例如，在一个数组中找到长度为 k 的所有子数组或子串。
- 可变大小的窗口：窗口大小根据某些条件动态变化，常用于寻找最小或最大符合条件的子数组。例如，找到和大于等于某个目标值的最小子数组。

适用的典型问题：

固定大小窗口：
- 子数组最大和问题：给定一个整数数组 nums 和一个整数 k，求所有大小为 k 的子数组的最大和。
- 长度为 k 的滑动窗口内的元素和。
可变大小窗口：
- 最小覆盖子串：给定一个字符串 s 和一个模式 p，找出 s 中包含 p 所有字符的最小子串。
- 最长子数组和：给定一个数组，找到子数组和小于等于某个目标值的最长子数组。
- 找出字符串中所有包含某些字符的最短子串。