【LeetCode热题100】滑动窗口

这篇博客总结了滑动窗口的8道常见题目，分别是：长度最小的子数组、无重复字符的最长子串、 最大连续1的个数III、将x减到0的最小操作数、水果成篮、找到字符串中所有字母异位词、串联所有单词的子串、最小覆盖子串。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int len = INT_MAX,left=0,right=0,sum=0;int n = nums.size();for(int left=0,right=0;right<n;right++){sum += nums[right];//进窗口while(sum >= target)//判断{len = min(len,right-left+1);sum -= nums[left++];//出窗口}}return len==INT_MAX?0:len;}
};

题目分析：这道题有两种解法：暴力解法和优雅解法。首先我们先从暴力解法说起，暴力枚举出所有子数组的和，定义left和right都指向数组第一个元素，求出left和right之间元素的和，然后固定left，right++，sum加上right指向的元素，然后继续right++，sum再加上right指向的元素，当sum>=taregt时，算出这时left和right之间元素个数，然后left继续右移，直到找到结尾，然后left++，继续right从此时的left开始继续往右走，直到找到所有的结果。

但是，暴力解法有很多可改进的区间，首先，当我们找到第一个sum>=taregt时的right，接着right后面的就不用遍历了，肯定不符合条件。然后，当left++后，此时我们不用把right移动到left的位置，只需要让之前的sum减去left上一个位置的值。利用这两点，我们的优雅解法的思路就是，利用单调性，使用“同向双指针”来优化，left和right都只向同一个方向移动，都不回退。同向双指针又称滑动窗口，滑动窗口用来维护区间的和，当两个指针都不回退时，就可以用滑动窗口。

那怎么用滑动窗口呢？1.设置左右窗口left=0和right=0  2.进窗口  3.根据进的窗口判断是否出窗口，循环23步。

滑动窗口的时间复杂度是O(N)。 

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = {0};int ret = 0;int n = s.size();for(int left = 0,right = 0;right<n;right++){hash[s[right]]++;//进窗口while(hash[s[right]] == 2)//判断hash[s[left++]]--;//出窗口ret = max(ret,right-left+1);//更新}return ret;}
};

题目分析：开始时，我们设置left和right都指向字符串的开始，然后right向右走，直到找到重复的字符串，然后让left++，一直跳过重复的字符串（使用哈希表判断有无重复字符），此时，我们还需要让right退回和left一样的位置重新遍历吗？不需要，因为left和right中间的肯定没有重复字符串，也就是说，在遍历的过程中，left和right都不需要回退，那么我们就可以使用滑动窗口的思想解决：

1.left=0,right=0

2.进窗口

3.判断

        出窗口

4.更新

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int cnt = 0;int size = nums.size();int len = 0;for(int left = 0,right = 0;right < size; right++){if(nums[right] == 0)//进窗口{cnt++;}while(cnt > k)//判断{if(nums[left] == 0)cnt--;left++;//出窗口}len = max(len,right-left+1);}return len;}
};

题目分析：题目可以转化为找出最长的子数组，其0的个数不超过k个，题目也是有两种解法：暴力解法和优雅解法。

暴力解法：暴力枚举每一个子数组，同时加上zero计数器（一个变量），通过判断zero的大小来判断这是不是符合要求的子数组。

优雅解法：left和right指向数组的开始，right向后遍历，当子数组中的0的个数为k+1时，left++，直到其间子数组0的个数为k，然后right继续向后++，直到最后。我们发现right和left都不需要回退，因此可以使用滑动窗口来解决。1.left = 0，right=0；2.进窗口 3.判断-出窗口-更新结果。

class Solution {
public:int minOperations(vector<int>& nums, int x) {long long s = 0;for(auto e:nums) s+=e;int target = s-x;if(target < 0) return -1;else if(target == 0) return nums.size();int len = 0;int n = nums.size();int sum = 0;for(int left = 0,right = 0;right<n;right++){//1.进窗口sum += nums[right];//2.判断while(sum > target){//出窗口sum -= nums[left++];}if(sum == target){len = max(len,right-left+1);}}return len == 0?-1:n-len;}
};

题目分析：这道题可以转化为找出最长的子数组的长度，所有元素的和正好等于sum-x。经过前面几道题的学习，我们可以明显感觉到可以用滑动窗口的思路解决。1.left=0,right=0 2.进窗口，sum+nums[right]，3.判断，是否窗口之间元素的和大于sum-x，如果是，出窗口，直到和≤sum-x，然后出循环后，继续判断是否和等于sum-x，然后依据情况更新len。

class Solution {
public:int totalFruit(vector<int>& fruits) {//map<int,int> m;int hash[100001] = {0};int len = 0;for(int left = 0,right =0,kinds=0;right<fruits.size();right++){if(hash[fruits[right]] == 0) kinds++;hash[fruits[right]]++;//进窗口while(kinds > 2)//判断{hash[fruits[left]]--;if(hash[fruits[left]] == 0) kinds--;left++;}len = max(len,right-left+1);}return len;}
};

题目分析：题目可以转化为，找出一个最长的子数组的长度，子数组中不超过两种类型的水果。为了判断子数组的水果种类，可以使用哈希表的思想。这道题经过暴力枚举思考后，也可以使用滑动窗口来解决。1.left=0，right=0  2.进窗口，hash[f[right]]++  3.判断，left和right之间水果种类是否超了，如果没有超，更新len，如果超了，出窗口。

class Solution {
public:bool check(int* cmp,int* target){for(int i = 0;i<26;i++){if(cmp[i] != target[i]) return false;}return true;}vector<int> findAnagrams(string s, string p) {int hash_target[26] =  {0};int hash_cmp[26] = {0};vector<int> ret;int count = 0;//窗口区间有效字符个数for(auto e:p){hash_target[e-'a']++;}for(int left = 0,right=0;right <s.size();right++){hash_cmp[s[right]-'a']++;//进窗口if(right - left + 1 > p.size())//判断{hash_cmp[s[left++]-'a']--;//出窗口}if(check(hash_cmp,hash_target)) ret.push_back(left);//更新结果}return ret;}
};

题目解析：首先我们先来想一想，给出两个字符串，如何判断它们是不是变位词，其实，只要这两个字符串中每种字符的个数一样即可。因此，我们可以创建两个哈希表，遍历这两个字符串，分别将这两个字符串中的字符放到哈希表中，最后遍历这两个哈希表，判断这两个哈希表中对应字符的个数是否相同。

好了，现在，我们需要在字符串s中，依次遍历出长度等于p长度的子串，然后判断这个子串是不是p的变位词，子串的长度我们一直要维护成p的长度，也就是子串长度一直不变，因此，我们可以采用滑动窗口的思想，但是，与之前滑动窗口所不同的是，这道题的滑动窗口长度固定。

1.left=0，right=0  2.进窗口，hash_cmp[in]++  3.判断，如果right-left+1>m，那么就需要出窗口hash_target[out]--  3.更新结果，检查这两个字符串的哈希表是否构成变位词。

在上面，我们比较这两个子串是否构成变位词，是通过比较两个哈希表，其实，我们还可以通过利用变量count来统计窗口中“有效字符”的个数，具体来说，在进窗口后，如果hash_cmp[in]<=hash_target[in]，count++；在进窗口前，如果hash_cmp[out]<=hash_target[out]，说明要出窗口的是有效字符，count--；然后再判断count==m，如果成立，说明窗口内就是p的变位词，更新结果。代码如下：

class Solution {
public:vector<int> findAnagrams(string s, string p) {int hash_target[26] =  {0};int hash_cmp[26] = {0};vector<int> ret;int count = 0;//窗口区间有效字符个数for(auto e:p){hash_target[e-'a']++;}for(int left = 0,right=0;right <s.size();right++){hash_cmp[s[right]-'a']++;//进窗口if(hash_cmp[s[right]-'a'] <= hash_target[s[right]-'a']) count++;if(right - left + 1 > p.size())//判断{if(hash_cmp[s[left]-'a'] <= hash_target[s[left] - 'a'])count--;hash_cmp[s[left++]-'a']--;//出窗口}if(count == p.size()) ret.push_back(left);//更新结果}return ret;}
};

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string,int> hash_target;int size = words[0].size();vector<int> ret;for(auto& e:words){hash_target[e]++;}for(int i = 0;i < size;i++)//执行size次滑动窗口{unordered_map<string,int> hash_cmp;//需要定义在这里，每次循环就是新的hash_cmpfor(int left = i,right = i,count=0;right + size <=s.size();right+=size){string in(string(s,right,size));hash_cmp[in]++;//进窗口if(hash_target.count(in) && hash_cmp[in] <= hash_target[in]) count++;if(((right - left)/size+1) > words.size())//判断{string out(string(s,left,size));//第一个条件判断如果out不存在，那么就不会执行后面的，就不会把out插入if(hash_target.count(out) && hash_cmp[out] <= hash_target[out]) count--;hash_cmp[out]--;left+=size;}if(count == words.size()) ret.push_back(left);}}return ret;}
};

题目解析：这道题和上面的一道题很类似，我们只需要把s中的几个字符看成一个，和上题不同的是：1.我们需要使用map<string,int>这样的容器，来统计区间所包含的字符串 2.left和right每次移动的步数是字符串的长度 3.除了让left=0和right=0,开始遍历外，还需要依次从left=1和right=1、left=2和right=2遍历（假设每个字符串长度为3）。

class Solution {
public:string minWindow(string s, string t) {int hash_target[128];int hash_cmp[128];int kinds = 0;//统计有效字符有多少种size_t len = INT_MAX;size_t begin = 0;for(auto e:t){if(hash_target[e] == 0){kinds++;}hash_target[e]++;}for(int left=0,right=0,count=0;right < s.size();right++){hash_cmp[s[right]]++;//进窗口if(hash_cmp[s[right]] == hash_target[s[right]]) count++;while(count == kinds)//判断{if(right-left+1 < len) //更新{len = right - left +1;begin = left;}if(hash_cmp[s[left]] == hash_target[s[left]]) count--;hash_cmp[s[left++]]--;//出窗口}}return len==INT_MAX?string(""):s.substr(begin,len);}
};

题目分析：在经过暴力枚举分析后，我们发现可以使用暴力枚举和哈希表的方式解决。把t中每个字符依次放到哈希表中得到hash_target，然后暴力枚举s中的子字符串，将子字符串依次放到hash_cmp中，比较这两个哈希表，如果hash_target中每个字符的数量<=hash_cmp中对应的每个字符的数量，就认为这个子字符串符合要求。在经过暴力枚举分析后，我们发现其实也可以用滑动窗口的思想解决，也是需要哈希表配合！步骤：1.left=0,right=0 2.进窗口，hash_cmp[in]++ 3.判断，看当前窗口是否符合要求，如果不符合，继续步骤2，如果符合，则出窗口。

然而，上面比较哈希表的开销比较大，我们再来想一种更优秀的办法来判断当前区间是否符合要求，定义count变量，用于标记有效字符的种类，count的使用方法是，在进窗口之后，当hash_cmp[in]==hash_target[in]时，说明这个字符的要求已经达到，有效字符种类count+1；在出窗口之后，当hash_cmp[out]==hash_target[out]时，说明在出完这个字符后，这个字符就不符合要求了，有效字符种类count-1，这样我们就可以通过判断count和t中字符种类是否相等来确定当前区间是否符合要求。