滑动窗口 -- 限制窗口内某元素的数量/种类

目录

长度最小的数组

题解：

将x减到0的最小操作数

题解：

 最大连续1的个数

题解：

 无重复字符的最长子串（限制数量）

题解：

水果成篮（限制种类）

题解：

找到字符串中所有字母异位词（限制数量和种类）

题解：

串联所有单词的子串

 题解：

最小覆盖子串

题解：

---

滑动窗口最重要的是如何调整窗口，如何调整 left 和 right！

长度最小的数组

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

题解：

由于题目要求找满足条件的子数组，这个子数组可以看成一个区间，我们可以利用左右指针，左指针指向这个区间的开始位置，右指针指向区间的结束位置，寻找满足条件的区间的过程，可以形象地看成一个窗口在数组内滑动。

左指针设为 left，右指针设为 right，以示例 1 为例，起始时 left 和 right 都指向下标为 0 的位置，此时窗口内的数只有 2，明显窗口内的总和小于 target，所以我们让 right 右移，left 不动，不断扩大这个窗口，让窗口内的总和不断增大，如下图所示：

当窗口内的总和大于 target 时，需要暂停下来思考一下。

由于题目规定数组的每一个元素都是正整数，所以 right 继续右移，窗口的长度越来越长，窗口内的总和一定会越来越大，离正确答案越来越远！所以这个时候需要对窗口进行调整，怎么调整呢？ 

调整的方法就是让 left 右移，让窗口缩小一点，那要缩小到什么时候就暂停呢？

当缩小到窗口内的和小于 target 时，left 就可以停止右移了，如果 left 继续右移，窗口内的和越来越小，又开始远离正确答案了。

如下图所示，当 left 右移到下标为 1 的位置时，窗口内的总和为 6，此时若 left 继续右移，窗口内的总和就越来越小了，离正确答案越来越远。

窗口调整完之后，right 就可以继续右移了，移动到窗口内的总和大于target 时，再调整一次窗口即可。

显然，当窗口内的总和等于 target 时，也需要停下来调整窗口，因为 right 继续右移，窗口内的总和又越来越大了，长度也越来越长，又开始远离正确答案了。

可以发现，当窗口内的总和大于等于 target 时，窗口的长度可能就是我们想要的答案，此时可以进行判断并更新结果。

总结：当窗口内的总和大于等于 target 时，我们就需要调整窗口的大小，在调整窗口前，更新一下答案。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum=0,ret=INT_MAX,n=nums.size();for(int left=0,right=0;right<n;right++){sum+=nums[right];while(sum>=target)//注意题目是大于等于{ret=min(ret,right-left+1);sum-=nums[left];    ++left;}}return ret==INT_MAX?0:ret;}
};

将x减到0的最小操作数

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

题解：

对于本题，将原数组掐头去尾，使去掉的数字的总和恰好为 x，换个角度想，假设数组的总和为 sum，将 x 减到 0 ，相当于让数组内的某个区间的总和为 sum-x，求出将 x 减为 0 的最小操作数，相当于求出使区间的总和为 sum-x 的最大长度，问题就转化为上一题的变形题，思路是类似的。 

如果 target = sum-x 的值小于 0 ，由于数组中的每个数都是正数，所以子数组的和不可能小于 0，所以子数组一定不存在。 

 注意如果数组内不存在这样的子数组，返回值为 -1.

在本道题中，我们假设 len 为窗口的长度，求出窗口的最大长度后，n - len就是将 x 减到 0 的最小操作数， len 的初始值应该设为多少呢？

如果设为 0，在leetcode 中，下面的数组是没办法通过的：

nums =  [8828,9581,49,9818,9974,9869,9991,10000,10000,10000,9999,9993,9904,8819,

  1231,6309] 

x = 134365

最终输出的结果为 -1，但实际答案为 16. 

为什么呢？nums 的总和恰好为 x，所以 target = sum - x = 0，这意味着初始时 right 和 left 指向同一个位置，tmp+=nums[ right ]，  tmp > target  成立，进入while 循环， left 也右移， left 在 right 的下一个位置，且把 tmp 修正为 0，跳出了 while 循环，此时 tmp == target，进入 if 判断，更新 len 的长度，更新 len 的长度时，len 为 0，right - left+1 也为 0，len 更新后依然为 0 。

更新完 len 之后 right++，left 和 right 又指向同一个位置，重复上面的步骤。

 这就导致当 right 把数组遍历完了，窗口也结束了，但是 len 仍为 0，最终判断返回值时，len 为 0，返回 -1.

return len==0?-1:n-len;

所以应该把 len 的初始值设为 -1，这样在更新 len 的长度时，len 被更新为 0。

len=max(len,right-left+1);

 最后判断返回值时，len = 0 ，不等于 -1，n - len=n，也就可以求出正确答案！

return len==-1?-1:n-len;

正确答案： 

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

 最大连续1的个数

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

题解：

这道题换个思路，就是求区间内 0 的个数不超过 k 的最大长度，用滑动窗口就可以解决，思路和前面一样！

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

 无重复字符的最长子串（限制数量）

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

题解：

无重复字符，意味着字符的出现次数为 1。同样用滑动窗口来解决这个问题。我们可以用数组记录访问到的字符的出现次数。

当 right 不断右移时，如果 right 位置的字符的出现次数为 2，此时就需要维护窗口了，需要让 left 右移，找到 right 位置的字符第一次出现的位置，并跳过它。

class Solution {
public:int lengthOfLongestSubstring(string s) {int ret=0,n=s.size(),left=0,right=0;//char hash[128]={0};用ASCII就可以int hash[128]={0};while(right<n){hash[s[right]]++;while(hash[s[right]]>1)//找到重复的字符并跳过{hash[s[left]]--;left++;}ret=max(ret,right-left+1);++right;}return ret;}
};

水果成篮（限制种类）

904. 水果成篮 - 力扣（LeetCode）

题解：

上一题要求没有重复的字符，即窗口内的字符只出现 1 次，限制字符的数量，这一题要求窗口内数字的种类只能为 2 种，即限制种类。

为什么需要用 map ，用 set 不可以吗？

当窗口内的数字的种类为 3 种时，我们需要维护窗口，即去掉其中一个种类，那怎么判断当前的窗口已经去掉一个种类了呢？用该种类在窗口中出现的次数来判断，让 left 不断右移，每右移一次，窗口内该字符出现的次数 -1，次数减到 0 时则说明该窗口已经没有这个数了！用 map 就可以实现这种索引的关系，set 则不行。

class Solution {
public:int totalFruit(vector<int>& fruits) {unordered_map<int,int> hash;int n=fruits.size(),left=0,right=0,ret=0;while(right<n){hash[fruits[right]]++;while(hash.size()>2){hash[fruits[left]]--;if(hash[fruits[left]]==0)hash.erase(fruits[left]);++left;}ret=max(ret,right-left+1);right++;}return ret;}
};

找到字符串中所有字母异位词（限制数量和种类）

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

题解：

因为所给的字符都是小写字母，用数组就可以统计字符出现的次数（哈希表的消耗比较大）。

如何统计字符出现的数量？

窗口还没超的情况下，对于 right 访问的字符：

1、如果该字符在 p 中也出现过，且该字符在窗口内的数量还不够，则该字符为有效字符，count++；

2、如果该字符在 p 中没有出现过，则不做处理。

在代码中如何表示字符在 p 中也出现过，且该字符在窗口内的数量还不够？

如果字符 ch 在 p 中出现过，则 hash1[ ch-'a' ] 一定大于 0，如果 ch 在 p 中没有出现过，则 hash1[ ch-'a' ] 一定为 0。

---

每当 right 访问一个字符时，我们就统计 right 访问的字符出现的次数，即 hash2[ s[right] -'a'] ++，此时 hash2[ s[right] -'a'] >0，

• 如果该字符在 p 中也出现过，则会有 hash2[s[right]-'a']<=hash1[s[right]-'a']，则 count++；
• 如果该字符在 p 中不存在，则一定有 hash2[s[right]-'a'] > hash1[s[right]-'a'] =0，所以 count 不需要+1.

 if(hash2[s[right]-'a']<=hash1[s[right]-'a'])count++;

如果窗口超了，只需要跳过一个字符，跳过字符时需要判断这个字符是不是有效字符，是的话 count--，不是的话 count 不用修改，left 右移。

如果窗口内有效字符的个数等于 p 的长度，说明找到了一个起始索引。 

class Solution {
public:vector<int> findAnagrams(string s, string p) {int hash2[26]={0},hash1[26]={0},n=s.size(),m=p.size();for(auto x:p) hash1[x-'a']++;//统计p中每个字母出现的次数vector<int> ret;for(int left=0,right=0,count=0;right<n;right++){hash2[s[right]-'a']++;if(hash2[s[right]-'a']<=hash1[s[right]-'a'])count++;//当前的字母为有效字母，且有效字符的个数还没达到，count++//如果为无效字母的话，hash1[s[right]-'a']=0，而hash2[s[right]-'a']>0，不会进入判断if(right-left+1>m)//窗口超了{if(hash2[s[left]-'a']<=hash1[s[left]-'a'])   count--;hash2[s[left]-'a']--;++left;//窗口右移}//窗口的长度和有效字符出现的次数相等if(count==m) ret.push_back(left);//找到了}return ret;}
};

串联所有单词的子串

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

 题解：

由于 words 中每个字符串的长度都是相同的，如果我们对 s 中的字符按照 words 中字符串的长度进行切割，就可以看作上一道题的变形。

我们可以把切分后的每组字符串看出一个整体， 相当于判断每一小组的字符串是否在 words 中出现过。

所以我们的工作就是切分并取出子串，可以用 substr 函数来取出子串，取出子串后的工作和上一题一样，判断是否为有效子串、数量是否匹配。

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string,int> hash1;for(auto& x:words) hash1[x]++;//统计words中字符串出现的次数int len=words[0].size(),m=words.size();//字符串的长度vector<int> ret;for(int i=0;i<len;i++){unordered_map<string,int> hash2;//注意right+len<=s.size()要取=for(int left=i,right=i,count=0;right+len<=s.size();right+=len){string in=s.substr(right,len);//取出子串hash2[in]++;if(hash1.count(in) && hash2[in]<=hash1[in])  count++;//判断是否为有效子串if(right-left+1>m*len)//超出窗口了{string out=s.substr(left,len);if(hash1.count(out) && hash2[out]<=hash1[out])count--;hash2[out]--;left+=len;}if(count==m) ret.push_back(left);}}return ret;}
};

最小覆盖子串

76. 最小覆盖子串 - 力扣（LeetCode）

题解：

由于是覆盖，意思就是，在 s 字符串中，t 中出现字符的种类都要有，但每个字符出现的次数可以大于等于 t 中字符出现的次数。

设置变量 kinds，当某字符在 s 中出现的次数等于在 t 中出现的次数时，kinds ++，意思是这个字符已经覆盖完毕了。

当所有的字符都覆盖完毕时，就可以更新结果，并且调整窗口。

调整窗口，只需要让 left 右移，直到某个字符没有被覆盖，就可以让 right 右移，继续寻找下一个目标。

class Solution {
public:string minWindow(string s, string t) {int hash1[128]={0},hash2[128]={0},kinds=0,begin=-1,minlen=INT_MAX;for(auto s:t) {if(hash1[s]==0) kinds++;//统计字符的种类hash1[s]++;//统计字符出现的次数}for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];hash2[in]++;if(hash1[in]==hash2[in]) count++;//字符出现的次数到了，有效字符的种类++while(count==kinds)//全部字符都凑齐了{if(right-left+1<minlen)//更新结果{minlen=right-left+1;    begin=left;}char out=s[left];if(hash2[out]==hash1[out])  count--;//跳过当前字符后，种类-1//即在[left,right]区间内，字符出现次数不足hash2[out]--;left++;}}if(begin==-1) return "";else    return s.substr(begin,minlen);}
};