专题二：滑动窗口【优选算法】

算法】"/>

专题二：滑动窗口【优选算法】

滑动窗口：

什么时候用？ 同向双指针（找单调性）

怎么用？

1）用left、right指针维护窗口

2）进窗口（right指针++，更新窗口内的值）

3）判断

        出窗口（left++，并更新窗口内的值）

4）更新结果（注意每道题更新结果的时机不同，需具体分析）

目录

滑动窗口：

1、长度最小的子数组

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

3、最大连续1的个数 

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

5、水果成篮

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

7、串联所有单词的子串(容器的使用）

8、最小覆盖子串 

1、长度最小的子数组

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

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

 暴力解法，枚举每一个字串，但分析可发现，出现重复字符时，left可直接跳到重复字符，right也无需往回走。因此就是同向双指针，也就是滑动窗口。

class Solution {
public:int lengthOfLongestSubstring(string s) {vector<int> hash(128);//用来判断字符是否出现过int len = 0,n = s.size();for(int l = 0,r = 0;r < n;r++){//进窗口hash[s[r]]++;while(hash[s[r]] > 1)//判断{hash[s[l]]--;//出窗口l++;}len = max(len,r-l+1);//更新结果}return len;}
};

3、最大连续1的个数 

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

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

通过正难则反，可以将此题转换成类似第一题 

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

5、水果成篮

 unordered_map版

class Solution {
public:int totalFruit(vector<int>& fruits) {unordered_map<int,int> hash;int n = fruits.size();int kind = 0,ret = 0;for(int left = 0,right= 0;right < n;right++){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);}return ret;}
};

数组版： 

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

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

check的优化： 

class Solution {
public:vector<int> findAnagrams(string s, string p) {int hashp[265] = {0};for(auto x : p) hashp[x]++;int count = 0;vector<int> ret;int hashs[256] = {0};for(int l = 0,r = 0;r < s.size();r++){hashs[s[r]]++;if(hashs[s[r]] <= hashp[s[r]]) count++;if(r - l + 1 > p.size()){if(hashs[s[l]] <= hashp[s[l]]) count--;hashs[s[l]]--;l++;}if(count == p.size()) ret.push_back(l);}return ret;}
};

7、串联所有单词的子串(容器的使用）

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string,int> hash1;vector<int> ret;for(auto& s:words){hash1[s]++;}int len = words[0].size(),m = words.size();for(int i = 0;i < len;i++){unordered_map<string,int> hash2;for(int left = i,right = i,count= 0; right + len <= s.size();right += len){//进窗口+维护countstring in = s.substr(right,len);hash2[in]++;if(hash2[in] <= hash1[in]) count++;//判断if(right - left + 1 > len * m) {//出窗口+维护countstring 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、最小覆盖子串 

class Solution {
public:string minWindow(string s, string t) {int hash1[128] = {0};int kinds = 0;//统计有效字符种类数for(auto ch : t) {if(hash1[ch] == 0) kinds++;hash1[ch]++;}int hash2[128] = {0};int minlen = INT_MAX,begin = -1;for(int left = 0,right = 0,count = 0;right < s.size();right++){//进窗口char in = s[right];hash2[in]++;if(hash2[in] == hash1[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--;hash2[out]--;}}if(begin == -1) return "";else return s.substr(begin,minlen);}
};