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) { // 窗口大小不足 kcontinue;}// 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 + 1ma = 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!