【leetcode】滑动窗口专题

1.长度最小的子数组

leetcode 209.长度最小的子数组

看到这个题目，第一眼肯定想到的是暴力枚举，那我们就来枚举以下试试：

很明显，暴力枚举的方式会超时。

那有没有哪里能优化一下，让它不超时呢？我们来分析一下：

在暴力枚举中，我们的 right 每次都会回到left位置的下一个，然后和 left 一起重新枚举。

优化枚举具体步骤如下：

在上面的枚举过程中，我们的蓝色框就像是一个滑动的、大小不固定的窗口，我们称这种方式叫做滑动窗口

对与滑动窗口而言，无非就以下几个步骤：

每个题目窗口的起始、更新结果的位置是不固定的，具体情况具体分析。

按照滑动窗口的方法，我们的代码就不会超时啦。

简单分析以下时间复杂度：从代码看好像是O(n²)，但是由于我们滑动窗口的思想，两个指针是同向遍历，而且不会回退；当right指针结束时，循环结束，所以它的时间复杂度是O(n)。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ret = INT_MAX;int n = nums.size();int sum = 0;for(int left = 0, right = 0; right < n; right++)//right后移{//进窗口sum += nums[right];//判断窗口while(sum >= target){//符合条件，更新结果ret = min(ret,right - left + 1);sum -= nums[left];//出窗口left++;}  }if(ret == INT_MAX)return 0;elsereturn ret;}
};

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

leetcode 3.无重复字符的最长字串

这一题首先想到的方法无疑就是枚举，然后统计每个字符出现的次数；如果一个字符出现了两次，那么当前字符对应的字符串就是最长子串

我们发现，暴力枚举法也可以过

那有没有更优的解法呢？我们来分析一下

上述解法不就是滑动窗口吗？

此时的时间复杂度O(n)是不是比暴力枚举O(n²)更加优秀了

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.size();int hash[128] = { 0 };int ret = 0;for(int left = 0, right = 0; right < n; right++){hash[s[right]]++;//入窗口，先记录当前while(hash[s[right]] > 1)//若s[right]重复{hash[s[left]]--;//出窗口left++;}ret = max(ret,right - left + 1);//更新结果}return ret;}
};

3.最大连续1的个数III

leetcode 1004.最大连续1的个数III

分析题目可知，其中0可以翻转的意思就是：0可以当作1来用。那我们的目标就是找一段包含1的个数最大连续的区间，该区间中0的个数不可以超过k。

这一题的暴力枚举法就不演示了，我们直接上滑动窗口。


这样我们的代码就过咯

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size();int zero = 0;//统计0的个数int ret = 0;for(int left = 0, right = 0; right < n; right++){//进窗口，判断是否是0if(nums[right] == 0)zero++;//判断0的个数是否大于kwhile(zero > k){//判断是否是0出窗口if(nums[left] == 0)zero--;left++;}//更新结果ret = max(ret,right-left+1);}return ret;}
};

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

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

通过读题我们可以发现，它一会是左边，一会是右边，是不是很难控制；那应该怎么做呢？
正难则反

• 我们在数组中找一块连续的区间，数组中去除该连续区间的内容，剩下的内容刚好等于x时，那我们是不是就找到了一种情况
• 该连续区间就是数组中元素的总和减去x
• 当在数组中找到的一块连续区间最长时，我们就找到了最佳的解决方案。

还是像前面的题目一样，使用滑动窗口。

class Solution {
public:int minOperations(vector<int>& nums, int x) {int ret = 0;int total = 0;int n = nums.size();for(auto e : nums)total += e; //求数组的和int target = total - x; //target为要找的连续区间的总大小if(target < 0)//细节return -1;if(total == x)return n;int sum = 0;for(int left = 0, right = 0; right < n; right++){sum += nums[right];//进窗口while(sum > target){sum -= nums[left];left++;}if(sum == target)//找到目标区间，取长的一个ret = max(ret,right - left + 1);}if(ret == 0)return -1;elsereturn n - ret;}
};

5.水果成篮

leetcode 904.水果成篮

这个题目这么长，它表达的是什么意思呢？

只有两个篮子，篮子里的水果只能有两种，并且不能跨越树木，求你所经过的树的最多的个数。
那又是求一段连续区间的长度，我们可以使用滑动窗口

那我怎么知道当前摘的水果有几种呢？----使用哈希表统计

我们可以发现，使用哈希表的消耗还是挺大的，能不能再优化一下呢？

由题目要求可知，种类是小于10⁵的，所以我们可以直接使用一个数组+一个变量（记录种类）

这样我们的效率就提升了很多。

class Solution {
public:int totalFruit(vector<int>& fruits) {int n = fruits.size();int ret = 0;int hash[100000] = { 0 };int kinds = 0;for(int left = 0, right = 0; right < n; right++){if(hash[fruits[right]] == 0)//判断是否是新种类水果kinds++;hash[fruits[right]]++;//进窗口while(kinds > 2)//判断总类是否大于2{hash[fruits[left]]--;//出窗口if(hash[fruits[left]] == 0)kinds--;  //去除该种类left++;}ret = max(ret,right - left + 1);}return ret;}
};

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

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

分析题目可知，就是在s串中找出p串（p串中的字符顺序可打乱）。
那我们就可以找一个长度和p相等，且字符种类、个数和p串相等的子串即可。

所以我们可以使用两个哈希表，分别统计p串和s串中字符的种类和个数。

那我们先使用暴力枚举的方式试一下：

那两个哈希表是如何进行比较的呢？

1. 首先使用hash1记录p串中字符的类型个数
2. 遍历s，找长度和p相等的子串，同时hash2存放当前字符
   a、若hash2[right] <= hash1[right]时，“有效字符”种类增加
   b、若hash2[right] > hash2[right]，“有效字符”种类不变

暴力枚举的方式确实可以过，但效率比较低下。
既然是找一段连续的区间，那能不能使用滑动窗口呢？我们来试一下

这样我们的效率就高很多了

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int len = p.size();int hash1[128] = { 0 };for(auto e: p)hash1[e]++;//统计p串的种类int n = s.size();int hash2[128] = { 0 };//统计子串种类int kinds = 0;int tmp = 0;for(int left = 0,right = 0; right < n ; right++){hash2[s[right]]++; //进窗口tmp++;//子串长度增加if(hash2[s[right]] <= hash1[s[right]])kinds++;//"有效字符"种类增加if(tmp > len){if(hash2[s[left]] <= hash1[s[left]])kinds--;//left位置为“有效字符”，种类减少hash2[s[left]]--;tmp--;left++;}if(tmp == len)if(kinds == len)ret.push_back(left);}return ret;}
};

7.串联所有单词的子串

leetcode 30.串联所有单词的子串

这一题和前一道题目类似，只不过这里是将字符换成了字符串而已。因此我们还是使用：滑动窗口+哈希表的方式解决。

解题步骤：

1. 先使用hash1统计words中字符串的种类
2. 使用滑动窗口(由于字符串的长度是固定的，所以可以直接跳跃长度)
   a、定义起始：left、right
   b、字符串进窗口，需要使用字符串的函数substr进行裁剪
   c、判断字符串的种类
     是否出窗口
     更新结果

然而，代码只过了一部分，分析一下它的测试用例发现，

这样代码就过啦！

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string,int> hash1;for(auto& e : words)hash1[e]++;//统计要求的字符串种类int n = s.size();int len = words[0].size();//固定的字符串长度int m = words.size();//数组长度for(int i=0; i < len; i++){unordered_map<string,int> hash2;int count = 0;for(int left = i, right = i; right <= n -len; right+= len){string in = s.substr(right,len);//裁剪字符串hash2[in]++;//进窗口if(hash2[in] <= hash1[in])count++;//统计当前字符串数量if(right - left + 1 > m*len)//判断字符串数量是否大于字符数组{string out = s.substr(left,len);if(hash2[out] <= hash1[out])count--;hash2[out]--;//出窗口left += len;}if(count == m)ret.push_back(left);}}return ret;}
};

8.最小覆盖子串

leetcode 76.最小覆盖子串

该题和上一题的解题思路差不多，也是在s串中找t串的全部字符，只不过这里要将找到的字符串的最小的一个返回而已。

我们依旧使用滑动窗口+哈希表的方式解决。

1. 使用hash1统计t串中字符的种类和数量
2. 滑动窗口：定义起始位置 left, right
   a、进窗口
   b、判断是否出窗口
   c、更新结果（仅需记录串的起始位置和长度，最后在切割子串）

在代码中在记录字符串的起始位置和长度即可，这样我们的代码就过啦。

class Solution {
public:string minWindow(string s, string t) {int hash1[128] = { 0 };for(auto e : t)hash1[e]++;//统计t串的字符种类和数量int m = t.size();int n = s.size();int hash2[128] = { 0 };int count = 0;int start = 0;int len = INT_MAX;for(int left = 0, right = 0; right < n; right++){hash2[s[right]]++;//进窗口if(hash2[s[right]] <= hash1[s[right]])//是否更新有效字符count++;while(count >= m)//是否出窗口{if(count == m)//找到符合种类的子串{//取长度小的一个int curlen = right - left + 1;if(curlen < len){start = left;len = curlen;}}//出窗口if(hash2[s[left]] <= hash1[s[left]])count--;hash2[s[left]]--;left++;}}if(len == INT_MAX)return "";elsereturn s.substr(start,len);}
};