定长滑动窗口和不定长滑动窗口

定长滑动窗口，题目一般会给我们长度为k

1.那么我们1先计算[0~k）第一个窗口里面的满足条件的

2.从i=k开始向右滑动窗口for(int i = k;i<n;i++);

这里我们算的是下标i从0往右移动逐渐循环每次遍历右边的k-1个数，

再判断窗口内的左边界[i-k],右边界[i]这两个数，因为我们移除的是左边的加入的是右边的，如果左边的满足条件，那满足条件而计算的一些贡献结果就要减掉，右边的满足条件贡献就要加上，

不用像暴力算法那样每次都要全部判断遍历整个窗口，提高效率

有时候也会需要使用到哈希表。

整数数组中长度为k的数组中所有的元素各不相同。（当题目要求：长度为 k 的子数组中所有元素互不相同）

需要结合滑动窗口和哈希表，unordered_map<数组元素类型，int>=cnt;

cnt<key>=val;key出现的次数，计算出现的次数和出现的元素，用哈希表计数可以快速判断窗口内是否有重复元素

哈希map = 计数+判重复

class Solution { public: long long maximumSubarraySum(vector<int>& nums, int k) { int n = nums.size(); long long current_sum = 0; long long max_sum = 0; unordered_map<int, int> cnt; // cnt[kay]=val;数字key出现的次数 long long unique_num = 0; for (int i = 0; i < k; i++) { if (cnt[nums[i]] == 0) { //如果之前没出现过，说明是新的唯一元素，unique_num 才会 +1。 unique_num++; } cnt[nums[i]]++;//把当前元素 nums[i] 加入哈希表，它的出现次数 +1 current_sum += nums[i]; if (unique_num == k) { max_sum = current_sum; } } for (int i = k; i < n; i++) { cnt[nums[i - k]]--; if (cnt[nums[i - k]] == 0) unique_num--; current_sum -= nums[i - k]; if (cnt[nums[i]] == 0) unique_num++; cnt[nums[i]]++; current_sum += nums[i]; if (unique_num == k) { max_sum = max(max_sum, current_sum); } } return max_sum; } };

不定长窗口（最长无重复子串）

必须使用set+双指针（left,right）

开始时left和right都是在数组下标为0的位置，但是left指针是不会动的，动的是右指针right。

right++,一直没有重复的数的时候就一直right++,出现重复时，left++,

class Solution { public: int lengthOfLongestSubstring(string s) { int n = s.size(); //两个指针，一开始都在最左边，然后右边的指针往右移动，左边的先不动，如果右边遇到重复的左边的再动 unordered_set<char>ooc; int max_len=0; int left = 0; for(int right=0;right<n;right++) { while(ooc.count(s[right])){ ooc.erase(s[left]); left++; }ooc.insert(s[right]); max_len=max(max_len,right-left+1); } return max_len; } };

不定长滑动窗口也会用到哈希map，这时候就要结合使用哈希map和left,right指针

1. 判断哈希表中键的数量 while(cnt.size() > ....) //限制种类

2. 判断哈希表中值的数量 while（ cnt[x] >1 ）;//无重复的判断

这里是针对题目给的数组有具体的数字要求

3. 去除某个数值 cnt.erase(数组名[下标]);

数量变为0时删掉他，保证不影响cnt,size(), if (cnt[...] == 0) cnt.erase(...);

4. 判断是否会有重复 while(cnt[数组名[数组下标]] > 1){}

//一般是用下标判断

1和4的逻辑是一样的

class Solution { public: int totalFruit(vector<int>& fruits) { int n = fruits.size(); int left = 0; int max_num = 0; unordered_map<int, int>cnt; for (int right = 0; right < n; right++) { cnt[fruits[right]]++;//这里直接加就好了 current_num++; while (cnt.size() > 2)//判断哈希表中键的数量 { cnt[fruits[left]]--; if (cnt[fruits[left]] == 0)//彻底减为0时再去除，不然会影响 { cnt.erase(fruits[left]); } left++;//左指针再向右移 } max_num = max(max_num, right - left + 1); } return max_num; } };

含有若干不同元素

while(cnt[nums[right]]>1) { cnt[nums[left]]--; current_sum-=nums[left]; if(cnt[nums[left]]==0){ cnt.erase(nums[left]); } left++; }

这里是一个数组中所有元素的频率都小于等于k

class Solution { public: int maxSubarrayLength(vector<int>& nums, int k) { int n = nums.size(); int left=0; int max_len =0; unordered_map<int,int>cnt; for(int right=0;right< n;right++) { cnt[nums[right]]++; while(cnt[nums[right]]>k)//k { cnt[nums[left]]--; if(cnt[nums[left]]==0) { cnt.erase(nums[left]); } left++; } max_len=max(max_len, right-left+1); } return max_len; } };

当窗口收缩到刚好不满足条件时
left 的值 = 以 right 结尾的合法子串数量
所以直接 count += left

求最多、不超过、完全合法
→ += right - left + 1
求至少包含、必须都有
→ += left

class Solution { public: int beautifulBouquet(vector<int>& flowers, int cnt) { int n = flowers.size(); int count=0; int left=0; unordered_map<int,int>c; for(int right=0;right<n;right++) { c[flowers[right]]++; while(c[flowers[right]]>cnt)//右指针元素出现的次数>cnt { c[flowers[left]]--; left++; } count+=right-left+1; } return count; } };

class Solution { public: int numberOfSubstrings(string s) { int n = s.size(); int count = 0; int left = 0; int a_num = 0; int b_num = 0; int c_num = 0; for (int right = 0; right < n; right++) { if (s[right] == 'a') { a_num++; } else if (s[right] == 'b') { b_num++; } else if (s[right] == 'c') { c_num++; } while (a_num >= 1 && b_num >= 1 && c_num >= 1) { if (s[left] == 'a') { a_num--; } else if (s[left] == 'b') { b_num--; } else if (s[left] == 'c') { c_num--; } left++; } count += left; } return count; } };