C++ 滑动窗口
前言
C++ 中滑动窗口分两种，一种是给定窗口长度，还有一种是不定长窗口长度。
本篇文章主要讲解这两种状态的滑动窗口，结合例题让读者更好的理解
一、给定窗口长度K
一般的，对于给定窗口长度的题，通常要求我们对窗口内的元素进行一些操作，解决一些问题，具体问题具体分析。
给定窗口长度的题目通常要求解决以下问题：
找到每个窗口内的最大值或最小值。
计算每个窗口的和或平均值。
统计满足条件的子数组数量。
找到满足条件的最长或最短子数组。
统计窗口内的唯一元素数量。
可以在 O(n) 的时间复杂度内解决问题
题目1：
力扣 1343 题大小为 K 且平均值大于等于阈值的子数组数目
给你一个整数数组 arr 和两个整数 k 和 threshold 。
请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。
示例 1：
输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
输出：3
解释：子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4，5 和 6 。其他长度为 3 的子数组的平均值都小于 4 （threshold 的值)。
示例 2：
输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
输出：6
解释：前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数
直接上代码：
class Solution {
public:
int numOfSubarrays(vector<int>& arr, int k, int threshold) {
int ans = 0;
int s = 0; // 维护窗口元素和
for (int i = 0; i < arr.size(); i++) {
// 1. 进入窗口
s += arr[i];
if (i < k - 1) { // 窗口大小不足 k
continue;
}
// 2. 更新答案
ans += s >= k * threshold;
// 3. 离开窗口
s -= arr[i - k + 1];
}
return ans;
}
};
解释：总共主要分3步，不足窗口长度的先进入窗口，满足长度等于窗口大小后更新答案，之后就是窗口往后移，右边元素进入窗口，左边元素移除窗口，然后不断更新答案。
题目2：
力扣2461题长度为 K 子数组中的最大和
给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
- 子数组的长度是
k，且 - 子数组中的所有元素 各不相同 。
返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。
子数组 是数组中一段连续非空的元素序列。
示例 1：
输入：nums = [1,5,4,2,9,9,9], k = 3 输出：15 解释：nums 中长度为 3 的子数组是： - [1,5,4] 满足全部条件，和为 10 。 - [5,4,2] 满足全部条件，和为 11 。 - [4,2,9] 满足全部条件，和为 15 。 - [2,9,9] 不满足全部条件，因为元素 9 出现重复。 - [9,9,9] 不满足全部条件，因为元素 9 出现重复。 因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。
示例 2：
输入：nums = [4,4,4], k = 3 输出：0 解释：nums 中长度为 3 的子数组是： - [4,4,4] 不满足全部条件，因为元素 4 出现重复。 因为不存在满足全部条件的子数组，所以返回 0 。
上代码看注释来理解
class Solution {
public:
long long maximumSubarraySum(vector<int>& nums, int k) {
int n = nums.size(); // 获取数组的长度
long long sum = 0; // 当前窗口的和
long long ma = 0; // 用于存储最大子数组和
unordered_map<int, int> hash; // 哈希表，用于记录窗口内每个元素的出现次数
// 初始化窗口的前 k-1 个元素
for (int i = 0; i < k - 1; i++) {
hash[nums[i]]++; // 更新元素的出现次数
sum += nums[i]; // 将元素加入当前窗口的和
}
// 遍历数组，维护一个大小为 k 的滑动窗口
for (int i = k - 1; i < n; i++) {
hash[nums[i]]++; // 将当前元素加入窗口，并更新其出现次数
sum += nums[i]; // 更新当前窗口的和
// 如果窗口内有 k 个不同的元素，更新最大和
if (hash.size() == k) {
ma = max(ma, sum); // 更新最大子数组和
}
// 移动窗口：移除窗口左侧的元素
hash[nums[i - k + 1]]--; // 减少左侧元素的出现次数
if (hash[nums[i - k + 1]] == 0) {
hash.erase(nums[i - k + 1]); // 如果元素的出现次数为 0，从哈希表中移除
}
sum -= nums[i - k + 1]; // 从当前窗口的和中移除左侧元素
}
return ma; // 返回最大子数组和
}
};逻辑解释：
初始化窗口：
使用一个哈希表
hash来记录窗口内每个元素的出现次数。使用
sum来记录当前窗口的和。首先将前
k-1个元素加入窗口，初始化sum和hash。滑动窗口遍历：
从第
k-1个元素开始遍历数组。每次将当前元素
nums[i]加入窗口，并更新其出现次数和窗口的和。检查窗口内是否有
k个不同的元素：
如果有
k个不同的元素，更新最大和ma。移动窗口：移除窗口左侧的元素
nums[i-k+1]，更新其出现次数和窗口的和。
如果某个元素的出现次数变为 0，从哈希表中移除该元素。
返回结果：
遍历结束后，
ma中存储的就是满足条件的最大子数组和。
二、不定长窗口大小
不定长滑动窗口主要分为三类：求最长子数组，求最短子数组，以及求子数组个数。
通常我们对于处理串的问题时，使用暴力算法超时的时候，就可以考虑使用滑动窗口来优化时间了
看题目来加深理解
题目1：
力扣904题水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
示例 1：
输入：fruits = [1,2,1] 输出：3 解释：可以采摘全部 3 棵树。
示例 2：
输入：fruits = [0,1,2,2] 输出：3 解释：可以采摘 [1,2,2] 这三棵树。 如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
示例 3：
输入：fruits = [1,2,3,2,2] 输出：4 解释：可以采摘 [2,3,2,2] 这四棵树。 如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4] 输出：5 解释：可以采摘 [1,2,1,1,2] 这五棵树。
AC代码
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int n = fruits.size(); // 获取果树的数量
unordered_map<int, int> hash; // 哈希表，用于记录当前窗口内每种水果的数量
int left = 0; // 滑动窗口的左边界
int ma = 0; // 用于记录最多可以采摘的水果数量
// 遍历所有果树，right 表示滑动窗口的右边界
for (int right = 0; right < n; right++) {
hash[fruits[right]]++; // 将当前果树的水果加入窗口，并更新其数量
// 如果窗口内有超过两种水果，需要收缩窗口
while (hash.size() > 2) {
int out = fruits[left]; // 获取窗口左侧的水果
hash[out]--; // 减少左侧水果的数量
if (hash[out] == 0) {
hash.erase(out); // 如果某种水果的数量变为 0，从哈希表中移除
}
left++; // 移动左边界，缩小窗口
}
// 更新最多可以采摘的水果数量
// 当前窗口的水果数量为 right - left + 1
ma = max(ma, right - left + 1);
}
return ma; // 返回最多可以采摘的水果数量
}
};很多题套路都差不多的，对于不定长滑动窗口大小，用的比较多的就是哈希表来存储
初始化：
n：果树的总数。
hash：哈希表，用于记录当前窗口内每种水果的数量。
left：滑动窗口的左边界，初始值为0。
ma：用于记录最多可以采摘的水果数量，初始值为0。滑动窗口遍历：
使用
right作为滑动窗口的右边界，从左到右遍历所有果树。每次将当前果树的水果加入窗口，并更新其在哈希表中的数量。
收缩窗口：
如果当前窗口内有超过两种水果（
hash.size() > 2），需要收缩窗口。移动左边界
left，移除窗口左侧的水果，直到窗口内只剩下两种水果。更新结果：
每次调整窗口后，计算当前窗口的水果数量（
right - left + 1），并更新最大值ma。返回结果：
遍历结束后，
ma中存储的就是最多可以采摘的水果数量。
题目2：
力扣1695题删除子数组的最大得分
给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。
返回 只删除一个 子数组可获得的 最大得分 。
如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。
示例 1：
输入：nums = [4,2,4,5,6] 输出：17 解释：最优子数组是 [2,4,5,6]
示例 2：
输入：nums = [5,2,1,2,5,2,1,2,5] 输出：8 解释：最优子数组是 [5,2,1] 或 [1,2,5]
这题和上题非常相识，都是同一个套路，变的就是题目给的条件
class Solution {
public:
int maximumUniqueSubarray(vector<int>& nums) {
int n = nums.size(); // 获取数组的长度
long long ma = 0; // 用于存储最大唯一子数组的和
int left = 0; // 滑动窗口的左边界
long long sum = 0; // 当前窗口内所有元素的和
unordered_map<int, int> hash; // 哈希表，用于记录窗口内每个元素的出现次数
// 遍历数组，right 表示滑动窗口的右边界
for (int right = 0; right < n; right++) {
// 将当前元素加入窗口，并更新其出现次数
hash[nums[right]]++;
sum += nums[right]; // 更新当前窗口的和
// 如果当前元素的出现次数大于 1，说明窗口内有重复元素
// 需要收缩窗口，移除窗口左侧的元素，直到窗口内没有重复元素
while (hash[nums[right]] > 1) {
sum -= nums[left]; // 从窗口的和中移除左侧元素
hash[nums[left]]--; // 更新左侧元素的出现次数
left++; // 移动左边界
}
// 更新最大唯一子数组的和
ma = max(ma, sum);
}
return ma; // 返回最大唯一子数组的和
}
};万变不离其宗，只有多刷题才能加深算法的印象。祝各位读者在刷算法的路上越走越远 0v0!