C++ 滑动窗口

例1

209. 长度���小的子数组

①窗口大小不固定

②求最小长度 -> ret = INT_MAX

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

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

参考代码

class Solution {public:    int minSubArrayLen(int target, vector& nums) {        int ret = INT_MAX;        for(int left = 0, right = 0, sum = 0; right = 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  1)            {                hash[s[left++]]--;            }            ret = max(ret, right - left + 1);        }        return ret;    }};

例3

1004. 最大连续1的个数 III

[right,  left]，有效闭区间

参考代码

class Solution {public:    int longestOnes(vector& nums, int k) {        int ret = 0;        for(int left = 0, right = 0, zero = 0; right  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& nums, int x) {        int sum = 0, ret = -1;        for(auto e : nums)            sum += e;        int target = sum - x;        if(target = 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& fruits) {        int hash[100001] = {0}, ret = 0;        for(int left = 0 ,right = 0 ,count = 0; right  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 findAnagrams(string s, string p) {        vector ret;        int hash1[128] = {0}, hash2[128] = {0};        for(auto e : p)            hash1[e]++;        for(int left = 0, right = 0, count = 0; right