一.定長滑動窗口
【套路】教你解決定長滑窗！適用于所有定長滑窗題目！
模版套路
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
)
