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 。注意均匀值不是整数
  直接上代码：

1. class Solution {
2. public:
3.     int numOfSubarrays(vector<int>& arr, int k, int threshold) {
4.         int ans = 0;
5.         int s = 0; // 维护窗口元素和
6.         for (int i = 0; i < arr.size(); i++) {
7.             // 1. 进入窗口
8.             s += arr[i];
9.             
10.             if (i < k - 1) { // 窗口大小不足 k
11.                 continue;
12.             }
13.             // 2. 更新答案
14.             ans += s >= k * threshold;
15.             // 3. 离开窗口
16.             s -= arr[i - k + 1];
17.         }
18.         return ans;
19.     }
20. };

复制代码

解释：总共主要分3步，不敷窗口长度的先进入窗口，满足长度等于窗口大小后更新答案，之后就是窗口往后移，右边元素进入窗口，左边元素移除窗口，然后不断更新答案。
标题2：

力扣2461题长度为 K 子数组中的最大和
给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

• 子数组的长度是 k，且
  
• 子数组中的全部元素 各不雷同 。
  

返回满足题面要求的最大子数组和。假如不存在子数组满足这些条件，返回 0 。
子数组 是数组中一段连续非空的元素序列。
示例 1：
  

1. <strong>输入：</strong>nums = [1,5,4,2,9,9,9], k = 3
2. <strong>输出：</strong>15
3. <strong>解释：</strong>nums 中长度为 3 的子数组是：
4. - [1,5,4] 满足全部条件，和为 10 。
5. - [5,4,2] 满足全部条件，和为 11 。
6. - [4,2,9] 满足全部条件，和为 15 。
7. - [2,9,9] 不满足全部条件，因为元素 9 出现重复。
8. - [9,9,9] 不满足全部条件，因为元素 9 出现重复。
9. 因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。

复制代码

示例 2：
  

1. <strong>输入：</strong>nums = [4,4,4], k = 3
2. <strong>输出：</strong>0
3. <strong>解释：</strong>nums 中长度为 3 的子数组是：
4. - [4,4,4] 不满足全部条件，因为元素 4 出现重复。
5. 因为不存在满足全部条件的子数组，所以返回 0 。

复制代码

上代码看解释来明白

1. class Solution {
2. public:
3.     long long maximumSubarraySum(vector<int>& nums, int k) {
4.         int n = nums.size();  // 获取数组的长度
5.         long long sum = 0;    // 当前窗口的和
6.         long long ma = 0;     // 用于存储最大子数组和
7.         unordered_map<int, int> hash;  // 哈希表，用于记录窗口内每个元素的出现次数
9.         // 初始化窗口的前 k-1 个元素
10.         for (int i = 0; i < k - 1; i++) {
11.             hash[nums[i]]++;  // 更新元素的出现次数
12.             sum += nums[i];   // 将元素加入当前窗口的和
13.         }
15.         // 遍历数组，维护一个大小为 k 的滑动窗口
16.         for (int i = k - 1; i < n; i++) {
17.             hash[nums[i]]++;  // 将当前元素加入窗口，并更新其出现次数
18.             sum += nums[i];   // 更新当前窗口的和
20.             // 如果窗口内有 k 个不同的元素，更新最大和
21.             if (hash.size() == k) {
22.                 ma = max(ma, sum);  // 更新最大子数组和
23.             }
25.             // 移动窗口：移除窗口左侧的元素
26.             hash[nums[i - k + 1]]--;  // 减少左侧元素的出现次数
27.             if (hash[nums[i - k + 1]] == 0) {
28.                 hash.erase(nums[i - k + 1]);  // 如果元素的出现次数为 0，从哈希表中移除
29.             }
30.             sum -= nums[i - k + 1];  // 从当前窗口的和中移除左侧元素
31.         }
33.         return ma;  // 返回最大子数组和
34.     }
35. };

复制代码

逻辑解释：
   

• 初始化窗口：
  
  
  
  • 使用一个哈希表 hash 来记录窗口内每个元素的出现次数。
    
  • 使用 sum 来记录当前窗口的和。
    
  • 起首将前 k-1 个元素加入窗口，初始化 sum 和 hash。
    
  
  
• 滑动窗口遍历：
  
  
  
  • 从第 k-1 个元素开始遍历数组。
    
  • 每次将当前元素 nums 加入窗口，并更新其出现次数和窗口的和。
    
  • 检查窗口内是否有 k 个不同的元素：
    
    
    
    • 假如有 k 个不同的元素，更新最大和 ma。
      
    
    
  • 移动窗口：移除窗口左侧的元素 nums[i-k+1]，更新其出现次数和窗口的和。
    
    
    
    • 假如某个元素的出现次数变为 0，从哈希表中移除该元素。
      
    
    
  
  
• 返回结果：
  
  
  
  • 遍历结束后，ma 中存储的就是满足条件的最大子数组和。
    
  
  

  二、不定长窗口大小

不定长滑动窗口主要分为三类：求最宗子数组，求最短子数组，以及求子数组个数。
通常我们对于处理串的问题时，使用暴力算法超时的时候，就可以思量使用滑动窗口来优化时间了
看标题来加深明白
标题1：

力扣904题水果成篮
你正在拜望一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，而且每个篮子只能装 单一范例 的水果。每个篮子能够装的水果总量没有限定。
  
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果范例。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
  
• 一旦你走到某棵树前，但水果不符合篮子的水果范例，那么就必须停止采摘。
  

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数量。
示例 1：
  

1. <strong>输入：</strong>fruits = [<em><strong>1,2,1</strong></em>]
2. <strong>输出：</strong>3
3. <strong>解释：</strong>可以采摘全部 3 棵树。

复制代码

示例 2：
  

1. <strong>输入：</strong>fruits = [0,<em><strong>1,2,2</strong></em>]
2. <strong>输出：</strong>3
3. <strong>解释：</strong>可以采摘 [1,2,2] 这三棵树。
4. 如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

复制代码

示例 3：
  

1. <strong>输入：</strong>fruits = [1,<em><strong>2,3,2,2</strong></em>]
2. <strong>输出：</strong>4
3. <strong>解释：</strong>可以采摘 [2,3,2,2] 这四棵树。
4. 如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

复制代码

示例 4：
  

1. <strong>输入：</strong>fruits = [3,3,3,<em><strong>1,2,1,1,2</strong></em>,3,3,4]
2. <strong>输出：</strong>5
3. <strong>解释：</strong>可以采摘 [1,2,1,1,2] 这五棵树。

复制代码

AC代码

1. class Solution {
2. public:
3.     int totalFruit(vector<int>& fruits) {
4.         int n = fruits.size();  // 获取果树的数量
5.         unordered_map<int, int> hash;  // 哈希表，用于记录当前窗口内每种水果的数量
6.         int left = 0;  // 滑动窗口的左边界
7.         int ma = 0;  // 用于记录最多可以采摘的水果数量
9.         // 遍历所有果树，right 表示滑动窗口的右边界
10.         for (int right = 0; right < n; right++) {
11.             hash[fruits[right]]++;  // 将当前果树的水果加入窗口，并更新其数量
13.             // 如果窗口内有超过两种水果，需要收缩窗口
14.             while (hash.size() > 2) {
15.                 int out = fruits[left];  // 获取窗口左侧的水果
16.                 hash[out]--;  // 减少左侧水果的数量
17.                 if (hash[out] == 0) {
18.                     hash.erase(out);  // 如果某种水果的数量变为 0，从哈希表中移除
19.                 }
20.                 left++;  // 移动左边界，缩小窗口
21.             }
23.             // 更新最多可以采摘的水果数量
24.             // 当前窗口的水果数量为 right - left + 1
25.             ma = max(ma, right - left + 1);
26.         }
28.         return ma;  // 返回最多可以采摘的水果数量
29.     }
30. };

复制代码

很多题套路都差不多的，对于不定长滑动窗口大小，用的比较多的就是哈希表来存储
   

• 初始化：
  
  
  
  • 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：
  

1. <strong>输入：</strong>nums = [4,2,4,5,6]
2. <strong>输出：</strong>17
3. <strong>解释：</strong>最优子数组是 [2,4,5,6]

复制代码

示例 2：
  

1. <strong>输入：</strong>nums = [5,2,1,2,5,2,1,2,5]
2. <strong>输出：</strong>8
3. <strong>解释：</strong>最优子数组是 [5,2,1] 或 [1,2,5]

复制代码

这题和上题非常相识，都是同一个套路，变的就是标题给的条件

1. class Solution {
2. public:
3.     int maximumUniqueSubarray(vector<int>& nums) {
4.         int n = nums.size();  // 获取数组的长度
5.         long long ma = 0;     // 用于存储最大唯一子数组的和
6.         int left = 0;         // 滑动窗口的左边界
7.         long long sum = 0;    // 当前窗口内所有元素的和
8.         unordered_map<int, int> hash;  // 哈希表，用于记录窗口内每个元素的出现次数
10.         // 遍历数组，right 表示滑动窗口的右边界
11.         for (int right = 0; right < n; right++) {
12.             // 将当前元素加入窗口，并更新其出现次数
13.             hash[nums[right]]++;
14.             sum += nums[right];  // 更新当前窗口的和
16.             // 如果当前元素的出现次数大于 1，说明窗口内有重复元素
17.             // 需要收缩窗口，移除窗口左侧的元素，直到窗口内没有重复元素
18.             while (hash[nums[right]] > 1) {
19.                 sum -= nums[left];  // 从窗口的和中移除左侧元素
20.                 hash[nums[left]]--;  // 更新左侧元素的出现次数
21.                 left++;  // 移动左边界
22.             }
24.             // 更新最大唯一子数组的和
25.             ma = max(ma, sum);
26.         }
28.         return ma;  // 返回最大唯一子数组的和
29.     }
30. };

复制代码

万变不离其宗，只有多刷题才能加深算法的印象。祝各位读者在刷算法的路上越走越远 0v0!




免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。