C++ 滑动窗口
前言C++ 中滑动窗口分两种，一种是给定窗口长度，另有一种是不定长窗口长度。
本篇文章主要解说这两种状态的滑动窗口，结合例题让读者更好的明白
一、给定窗口长度K
一般的，对于给定窗口长度的题，通常要求我们对窗口内的元素举行一些操作，办理一些问题，具体问题具体分析。
给定窗口长度的标题通常要求办理以下问题：
[*] 找到每个窗口内的最大值或最小值。
[*] 计算每个窗口的和或均匀值。
[*] 统计满足条件的子数组数量。
[*] 找到满足条件的最长或最短子数组。
[*] 统计窗口内的唯一元素数量。
可以在 O(n) 的时间复杂度内办理问题
标题1：
力扣 1343 题大小为 K 且均匀值大于等于阈值的子数组数量
给你一个整数数组 arr 和两个整数 k 和 threshold 。
请你返回长度为 k 且均匀值大于等于 threshold 的子数组数量。
示例 1：
输入：arr = , k = 3, threshold = 4
输出：3
解释：子数组 , 和 的均匀值分别为 4，5 和 6 。其他长度为 3 的子数组的均匀值都小于 4 （threshold 的值)。
示例 2：
输入：arr = , 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;
if (i < k - 1) { // 窗口大小不足 k
continue;
}
// 2. 更新答案
ans += s >= k * threshold;
// 3. 离开窗口
s -= arr;
}
return ans;
}
};
解释：总共主要分3步，不敷窗口长度的先进入窗口，满足长度等于窗口大小后更新答案，之后就是窗口往后移，右边元素进入窗口，左边元素移除窗口，然后不断更新答案。
标题2：
力扣2461题长度为 K 子数组中的最大和
给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
[*]子数组的长度是 k，且
[*]子数组中的全部元素 各不雷同 。
返回满足题面要求的最大子数组和。假如不存在子数组满足这些条件，返回 0 。
子数组 是数组中一段连续非空的元素序列。
示例 1：
<strong>输入：</strong>nums = , k = 3
<strong>输出：</strong>15
<strong>解释：</strong>nums 中长度为 3 的子数组是：
- 满足全部条件，和为 10 。
- 满足全部条件，和为 11 。
- 满足全部条件，和为 15 。
- 不满足全部条件，因为元素 9 出现重复。
- 不满足全部条件，因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。
示例 2：
<strong>输入：</strong>nums = , k = 3
<strong>输出：</strong>0
<strong>解释：</strong>nums 中长度为 3 的子数组是：
- 不满足全部条件，因为元素 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]++;// 更新元素的出现次数
sum += nums; // 将元素加入当前窗口的和
}
// 遍历数组，维护一个大小为 k 的滑动窗口
for (int i = k - 1; i < n; i++) {
hash]++;// 将当前元素加入窗口，并更新其出现次数
sum += nums; // 更新当前窗口的和
// 如果窗口内有 k 个不同的元素，更新最大和
if (hash.size() == k) {
ma = max(ma, sum);// 更新最大子数组和
}
// 移动窗口：移除窗口左侧的元素
hash]--;// 减少左侧元素的出现次数
if (hash] == 0) {
hash.erase(nums);// 如果元素的出现次数为 0，从哈希表中移除
}
sum -= nums;// 从当前窗口的和中移除左侧元素
}
return ma;// 返回最大子数组和
}
}; 逻辑解释：
[*] 初始化窗口：
[*] 使用一个哈希表 hash 来记录窗口内每个元素的出现次数。
[*] 使用 sum 来记录当前窗口的和。
[*] 起首将前 k-1 个元素加入窗口，初始化 sum 和 hash。
[*] 滑动窗口遍历：
[*] 从第 k-1 个元素开始遍历数组。
[*] 每次将当前元素 nums 加入窗口，并更新其出现次数和窗口的和。
[*] 检查窗口内是否有 k 个不同的元素：
[*] 假如有 k 个不同的元素，更新最大和 ma。
[*] 移动窗口：移除窗口左侧的元素 nums，更新其出现次数和窗口的和。
[*] 假如某个元素的出现次数变为 0，从哈希表中移除该元素。
[*] 返回结果：
[*] 遍历结束后，ma 中存储的就是满足条件的最大子数组和。
二、不定长窗口大小
不定长滑动窗口主要分为三类：求最宗子数组，求最短子数组，以及求子数组个数。
通常我们对于处理串的问题时，使用暴力算法超时的时候，就可以思量使用滑动窗口来优化时间了
看标题来加深明白
标题1：
力扣904题水果成篮
你正在拜望一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
[*]你只有 两个 篮子，而且每个篮子只能装 单一范例 的水果。每个篮子能够装的水果总量没有限定。
[*]你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果范例。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
[*]一旦你走到某棵树前，但水果不符合篮子的水果范例，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数量。
示例 1：
<strong>输入：</strong>fruits = [<em><strong>1,2,1</strong></em>]
<strong>输出：</strong>3
<strong>解释：</strong>可以采摘全部 3 棵树。
示例 2：
<strong>输入：</strong>fruits =
<strong>输出：</strong>3
<strong>解释：</strong>可以采摘 这三棵树。
如果从第一棵树开始采摘，则只能采摘 这两棵树。
示例 3：
<strong>输入：</strong>fruits =
<strong>输出：</strong>4
<strong>解释：</strong>可以采摘 这四棵树。
如果从第一棵树开始采摘，则只能采摘 这两棵树。
示例 4：
<strong>输入：</strong>fruits =
<strong>输出：</strong>5
<strong>解释：</strong>可以采摘 这五棵树。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]++;// 将当前果树的水果加入窗口，并更新其数量
// 如果窗口内有超过两种水果，需要收缩窗口
while (hash.size() > 2) {
int out = fruits;// 获取窗口左侧的水果
hash--;// 减少左侧水果的数量
if (hash == 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,a,...,a ，那么它就是 a 的一个子数组。
示例 1：
<strong>输入：</strong>nums =
<strong>输出：</strong>17
<strong>解释：</strong>最优子数组是
示例 2：
<strong>输入：</strong>nums =
<strong>输出：</strong>8
<strong>解释：</strong>最优子数组是 或 这题和上题非常相识，都是同一个套路，变的就是标题给的条件
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]++;
sum += nums;// 更新当前窗口的和
// 如果当前元素的出现次数大于 1，说明窗口内有重复元素
// 需要收缩窗口，移除窗口左侧的元素，直到窗口内没有重复元素
while (hash] > 1) {
sum -= nums;// 从窗口的和中移除左侧元素
hash]--;// 更新左侧元素的出现次数
left++;// 移动左边界
}
// 更新最大唯一子数组的和
ma = max(ma, sum);
}
return ma;// 返回最大唯一子数组的和
}
}; 万变不离其宗，只有多刷题才能加深算法的印象。祝各位读者在刷算法的路上越走越远 0v0!
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]