每日算法刷题计划Day7 5.15:leetcode滑动窗口4道题，用时1h

一.定长滑动窗口

【套路】教你解决定长滑窗！适用于所有定长滑窗题目！

模版套路

1.题目描述

1.计算所有长度恰好为 k 的子串中，最多可以包含多少个元音字母
2.找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
3.返回长度为 k 且平均值大于等于 threshold 的子数组数目
4.构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。(长度为2*k+1,更新位置为i-k)

2.套路
三步走:入窗口-更新答案-出窗口

• 1.入窗口:下标为i的元素进入窗口，更新相关统计量。如果i<k-1,则说明第一个窗口还未出现，重复步骤1.
• 2.更新答案，一般是更新最大值/最小值
• 3.出窗口，下标为i-k+1的元素离开窗口，更新相关统计量。
  c++:

class Solution {
public:int maxVowels(string s, int k) {int res = 0, cnt = 0;for (int i = 0; i < s.size(); ++i) {// 1.入窗口if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' ||s[i] == 'u') {// 更新统计量cnt++;}// 1. 第一个窗口未出现，重复步骤1if (i < k - 1) {continue;}// 2.更新答案res = max(res, cnt);// 3.出窗口if (s[i - k + 1] == 'a' || s[i - k + 1] == 'e' ||s[i - k + 1] == 'i' || s[i - k + 1] == 'o' ||s[i - k + 1] == 'u') {// 更新统计量cnt--;}}return res;}
};

python:

class Solution:def maxVowels(self, s: str, k: int) -> int:res, cnt = 0, 0for i in range(len(s)):# 1.入窗口if s[i] == "a" or s[i] == "e" or s[i] == "i" or s[i] == "o" or s[i] == "u":# 更新统计量cnt += 1# 1.第一个窗口未出现，重复步骤1if i < k - 1:continue# 2.更新答案res = max(res, cnt)# 3.出窗口if (s[i - k + 1] == "a"or s[i - k + 1] == "e"or s[i - k + 1] == "i"or s[i - k + 1] == "o"or s[i - k + 1] == "u"):# 更新统计量cnt -= 1return res

1. 1456.定长子串中元音的最大数目(中等)

1456. 定长子串中元音的最大数目 - 力扣（LeetCode）
同模版套路

2. 643.子数组最大平均数I(简单)

思想

找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
同套路

代码

c++:

class Solution {
public:double findMaxAverage(vector<int>& nums, int k) {double res = -1e5;int sum = 0;for (int i = 0; i < nums.size(); ++i) {sum += nums[i];if (i < k - 1)continue;res = max(res, (double)sum / k);sum -= nums[i - k + 1];}return res;}
};

优化:
循环内只更新res为sum,最终返回结果除以k即可，因为是定长窗口

3. 1343.大小为K且平均值大于等于阈值的子数组数目(中等)

1343. 大小为 K 且平均值大于等于阈值的子数组数目 - 力扣（LeetCode）

思想

返回长度为 k 且平均值大于等于 threshold 的子数组数目。
同套路一样

代码

c++:

class Solution {
public:int numOfSubarrays(vector<int>& arr, int k, int threshold) {int res = 0, sum = 0;for (int i = 0; i < arr.size(); ++i) {sum += arr[i];if (i < k - 1)continue;if (sum >= k * threshold)res++;sum -= arr[i - k + 1];}return res;}
};

4. 2090.半径为k的子数组平均值(中等)

2090. 半径为 k 的子数组平均值 - 力扣（LeetCode）

思想

1.构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。
2.注意:长度为2*k+1,更新位置为i-k

代码

c++:

class Solution {
public:vector<int> getAverages(vector<int>& nums, int k) {int n = nums.size();vector<int> res(n);for (int i = 0; i < n; ++i)res[i] = -1;int len = 2 * k + 1; // 定义一个lenlong long sum = 0;for (int i = 0; i < n; ++i) {sum += (long long)nums[i];if (i < len - 1)continue;res[i - k] = (double)sum / len;sum -= (long long)nums[i - len + 1];}return res;}
};

注意:
sum记得开long long