C++ 滑动窗口

例1

209. 长度最小的子数组

①窗口大小不固定

②求最小长度 -> ret = INT_MAX

③数组内的值都大于0， 符合单调性（sum  +=  nums[right] -> sum增大）

while里面符合条件，在里面更改ret

参考代码

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

例2

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

while里面是不符合条件的，外面与ret比较就行

参考代码

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = {0};int ret = 0;for(int left = 0, right = 0; right < s.size(); right++){hash[s[right]]++;while(hash[s[right]] > 1){hash[s[left++]]--;}ret = max(ret, right - left + 1);}return ret;}
};

例3

1004. 最大连续1的个数 III

[right,  left]，有效闭区间

参考代码

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

例4

转换为求中间最大长度

如果要用注释掉的部分，就要写上target == 0，因为while(tmp >= target) 会left++，这里的==会导致left越界，所以分开写较好，把满足条件的放在外面

参考代码

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum = 0, ret = -1;for(auto e : nums)sum += e;int target = sum - x;if(target < 0) return -1;// if(target == 0) return nums.size();//for(int left = 0, right = 0, tmp = 0; right < nums.size(); right++){tmp += nums[right];// while(tmp >= target)//☆☆☆☆☆// {//     if(tmp == target)//         ret = max(ret, right - left + 1);//     tmp -= nums[left++];//==的时候越界最后一次// }while(tmp > target) tmp -= nums[left++];if(tmp == target) ret = max(ret, right - left + 1);}return ret == -1 ? -1 : nums.size() - ret;}
};

例5

904. 水果成篮

后面的题都用到哈希映射

分析：哈希的临界点是从0 -> 1 和从 1 -> 0

语法：--hash[fruits[left++]] ，看括号，里面的优先，外面括号的前置“++”，“--” 往后稍稍，所以hash的索引是fruit[left]，再是left自增，再是--hash[fruit[left]]

参考代码

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

例6

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

分析：因为是固定窗口，所以：if(right - left + 1 > p.size())用的是if，只用右移一次left

语法分析：

①代码是全都拆开

②后置++ 和后置 -- ，在这里，两个写一起是不对的，因为右操作数例有left，：顺序是这样的：显示返回hash2[s[left],然后left++，然后hash2[s[left]]--，这时候left已经变大了1，导致左右两边left不是相同的值

③和⑤可以统一left

②③和④⑤是后置-- 和前置-- 的区别，所以判断条件也会不同。个人觉得后置的更好直接理解

参考代码

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[128] = {0}, hash2[128] = {0};for(auto e : p)hash1[e]++;for(int left = 0, right = 0, count = 0; right < s.size(); right++){if(++hash2[s[right]] <= hash1[s[right]]) count++;if(right - left + 1 > p.size()){// if(hash2[s[left]] <= hash1[s[left]]) count--;    1// hash2[s[left]]--;// left++;//if(hash2[s[left++]]-- <= hash1[s[left]]) count--;不对先++ 2// if(hash2[s[left]]-- <= hash1[s[left]]) count--;    3// left++;//if(--hash2[s[left++]] < hash1[s[left]]) count--;//不行   4//这里的后缀++比前置的--优先级高if(--hash2[s[left]] < hash1[s[left]]) count--;    //5left++;}if(count == p.size())ret.push_back(left);}return ret;}
};

例7

分析：对比上题就是把字符换成了字符串，那就只能用unordered_map<string, int>,

题目说了words里面的每个元素的长度相同，次数：words[0].size()

注意 left，right = i，不是=0，不然会ret是重复的数组

对于这行代码： if(hash1.count(in) && ++hash2[in] <= hash1[in]) count++;如果hash1[in]没有这个in，那么会自己创建一个，会浪费时间，前面加上hash1.count(in)判断，可以减少时间的消耗

参考代码

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string, int> hash1;vector<int> ret;for(auto e : words)hash1[e]++;int len = words[0].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){string in(s.substr(right, len));if(hash1.count(in) && ++hash2[in] <= hash1[in]) count++;if(right - left + len - 1>= words.size() * len){string out(s.substr(left, len));if(hash1.count(out) && hash2[out]-- <= hash1[out]) count--;left += len;}if(count == words.size())ret.push_back(left);}       }return ret;}
};

例8

76. 最小覆盖子串

①ret = min(ret, right - left + 1), begin = left;

②if(right - left + 1 < ret)  {ret = right - left + 1;begin = left;}

①②两段代码是有区别的： 上面不管ret是否变化，begin就会改变

                                            下面的，ret变小了才会变化

依据上面的题目知道这里的left++是不能写在里面的

if(hash2[s[left]]-- <= hash1[s[left]]) count--;left++;

注：这里是求最小长度，那么窗口肯定是变化的，肯定是while

参考代码

class Solution {
public:string minWindow(string s, string t) {int hash1[128] = {0}, hash2[128] = {0}, ret = INT_MAX, begin = -1;for(auto e : t)hash1[e]++;for(int left = 0, right = 0, count = 0; right < s.size(); right++){if(++hash2[s[right]] <= hash1[s[right]]) count++;while(count == t.size()){// ret = min(ret, right - left + 1), begin = left;if(right - left + 1 < ret){ret = right - left + 1;begin = left;}if(hash2[s[left]]-- <= hash1[s[left]]) count--;left++;}}return ret == INT_MAX ? "" : s.substr(begin, ret);}
};