定长滑动窗口--灵神题单（一刷基础）
目录
第一题：1456. 定长子串中元音的最大数目 - 力扣（LeetCode）
第二题：643. 子数组最大平均数 I - 力扣（LeetCode）
第三题：1343. 大小为 K 且平均值大于等于阈值的子数组数目 - 力扣（LeetCode）
第四题：2090. 半径为 k 的子数组平均值 - 力扣（LeetCode）
第五题：2379. 得到 K 个黑块的最少涂色次数 - 力扣（LeetCode）
第六题：1461. 检查一个字符串是否包含所有长度为 K 的二进制子串 - 力扣（LeetCode）
第七题：2841. 几乎唯一子数组的最大和 - 力扣（LeetCode）
第八题：2461. 长度为 K 子数组中的最大和 - 力扣（LeetCode）
第九题：1423. 可获得的最大点数 - 力扣（LeetCode）
简单介绍定长滑动窗口
首先我们先介绍一下滑动窗口的第一类型--定长；
这里的介绍我就直接截图截取灵神写的题解了。
对于出窗口的判断条件就是唯一的就是有边界-左边界+1>=限定长度。
本文章大致思路为：先给出题目，如果题目比较难理解，在给出解释。然后给出少些思路，然后你自己去思考剩余部分，自己写代码。最后在给出代码，如果代码的效率低也会给出相应的优化。
第一题：1456. 定长子串中元音的最大数目 - 力扣（LeetCode）
- 滑动窗口：使用两个指针（
left和right）表示窗口，right逐步扩展窗口，left在窗口大小达到k时收缩。 - 维护元音计数：在窗口中维护元音字符的计数，随着窗口的移动，更新计数并记录最大值。
class Solution {
public:
bool isVowel(char ch)
{
if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') return true;
return false;
}
int ret = 0;
int maxVowels(string s, int k) {
int n = s.size();
for (int left = 0, right = 0, count = 0; right < n; right++)
{
// 进窗口
if (isVowel(s[right])) count++;
// 判断出
if (right - left + 1 >= k)
{
ret = max(ret, count);
if (isVowel(s[left++])) count--;
}
}
return ret;
}
};第二题：643. 子数组最大平均数 I - 力扣（LeetCode）
- 滑动窗口：使用两个指针，
i表示窗口的结束位置，窗口大小固定为k，通过每次滑动更新窗口的和。 - 更新最大和：计算每个窗口的和，并保持记录窗口和的最大值，最后返回最大和的平均值。
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int sum = 0;
int n = nums.size();
for (int i = 0; i < k; i++) {
sum += nums[i];
}
int maxSum = sum;
for (int i = k; i < n; i++) {
sum = sum - nums[i - k] + nums[i];
maxSum = max(maxSum, sum);
}
return static_cast<double>(maxSum) / k;
}
};
第三题：1343. 大小为 K 且平均值大于等于阈值的子数组数目 - 力扣（LeetCode）
- 滑动窗口：使用
left和right两个指针表示窗口，right扩展窗口并累加元素，left收缩窗口保持大小为k。 - 计算平均值并判断：当窗口大小达到
k时，计算窗口的平均值并判断是否大于等于threshold，如果满足条件则计数。
第四题：2090. 半径为 k 的子数组平均值 - 力扣（LeetCode）
- 滑动窗口：首先计算窗口的初始和（窗口大小为
2k+1），然后滑动窗口更新和，通过移除最左边的元素并加入最右边的新元素。 - 计算平均值并填充结果：在每个有效窗口中，计算窗口的平均值并更新结果数组
ret。对于无法形成完整窗口的位置，返回-1。
class Solution {
public:
vector<int> getAverages(vector<int>& nums, int k) {
int n=nums.size();
long long sum=0;
int k1=2*k+1;
vector<int> ret(n,-1);
if (k1 > n) return ret;
for (int i = 0; i < k1 && i < n; i++) {
sum += nums[i];
}
for (int i = k; i < n - k; i++) {
// 计算窗口的平均值
ret[i] = sum / k1;
// 滑动窗口：去掉窗口最左边的元素，加入最右边的新元素
if (i + k <= n) {
sum -= nums[i - k]; // 去掉左边的元素
if(i+1<n-k) sum += nums[i + k + 1]; // 加入右边的元素
}
}
return ret;
}
};第五题：2379. 得到 K 个黑块的最少涂色次数 - 力扣（LeetCode）
- 滑动窗口：使用
left和right两个指针，right扩展窗口并统计窗口中白色块（'W'）的数量，当窗口大小达到k时，检查并更新最小白色块数。 - 更新最小值：在每次窗口大小为
k时，计算当前窗口中白色块的数量，并更新最小值ret，然后收缩窗口以继续寻找最优解。
class Solution {
public:
int minimumRecolors(string blocks, int k) {
int n = blocks.size();
int ret = n;
for (int left = 0, right = 0, count = 0; right < n; right++)
{
if (blocks[right] == 'W') count++;
while (right - left + 1 >= k)
{
ret = min(ret, count);
if (blocks[left++] == 'W') count--;
}
}
return ret;
}
};第六题：1461. 检查一个字符串是否包含所有长度为 K 的二进制子串 - 力扣（LeetCode）
- 滑动窗口：使用一个滑动窗口大小为
k，通过不断滑动窗口并计算每个子串对应的二进制值来收集所有可能的子串（子串的个数为2^k）。 - 哈希集合：将每个子串的二进制数转换为整数，并存入哈希集合中，最后检查哈希集合的大小是否等于
2^k，即是否包含了所有可能的二进制子串。
第七题：2841. 几乎唯一子数组的最大和 - 力扣（LeetCode）
- 滑动窗口：使用
left和right两个指针表示窗口，right扩展窗口并更新窗口内的和和元素计数，left收缩窗口以维持有效窗口大小。 - 更新结果：在窗口大小大于等于
k时，检查当前窗口中不同元素的数量（通过cnt.size()），如果满足条件（不同元素数大于等于m），更新最大和ret。
class Solution {
public:
long long maxSum(vector<int>& nums, int m, int k) {
int n=nums.size();
long long ret=0;
long long sum=0;
unordered_map<int, int> cnt;
for(int left=0,right=0;right<n;right++)
{
// 进窗口
sum+=nums[right];
cnt[nums[right]]++;
// 判断出
while(right-left+1>=k)
{
// 判断是否更新结果
if (cnt.size() >= m)
{
ret = max(ret, sum);
}
// 出
cnt[nums[left]]--;
if (cnt[nums[left]] == 0) cnt.erase(nums[left]);
sum-=nums[left++];
}
}
return ret;
}
};第八题：2461. 长度为 K 子数组中的最大和 - 力扣（LeetCode）
这一道题稍微说的详细一点，给出两种写法。
其中第一种写法也是最容易想到的，就是不去想任何特殊的优化处理，直接模拟
- 滑动窗口：使用
left和right两个指针表示窗口，right扩展窗口并更新窗口内的和和元素计数，left收缩窗口保持大小为k，确保窗口中没有重复的元素。 - 更新结果：每当窗口大小为
k且没有重复元素时，更新最大子数组和res。通过cnt哈希表维护每个元素的出现次数，cf记录重复元素的数量。
class Solution {
public:
long long maximumSubarraySum(vector<int>& nums, int k) {
long long res = 0;
int n = nums.size();
long long curs = 0;
unordered_map<int, int> cnt;
int cf = 0;
for (int r = 0, l = 0; r < n; r ++) {
curs += nums[r];
cnt[nums[r]] ++;
if (cnt[nums[r]] == 2) cf ++;
if (r - l + 1 > k) {
curs -= nums[l];
cnt[nums[l]] --;
if (cnt[nums[l]] == 1) cf --;
l++;
}
if (r - l + 1 == k) {
if (cf == 0) res = max(res, curs);
}
}
return res;
}
};但是这样的时间复杂度与空间复杂度都很差。
那么就需要优化，首先应该去想哪里造成了时间与空间慢。可以明显看到对于哈希表的map要选择优化，我们第一次采用的优化策略为：转用位图。其实我第一次写的代码就是方法一，也是看了别人写的题解，才明白，妙！太妙了！
-
滑动窗口：使用
st（窗口的起始位置）和i（窗口的结束位置）两个指针，i扩展窗口并更新当前子数组的和。通过bitset数据结构追踪窗口中每个元素是否存在，以确保窗口内没有重复元素。 -
更新结果：每当窗口大小大于或等于
k且不包含重复元素时，更新最大子数组和rt。如果遇到重复元素，收缩窗口（通过移动st）直到没有重复元素为止。
class Solution {
public:
long long maximumSubarraySum(vector<int>& nums, int k) {
bitset<100001> mySet;
long long tempSum = 0;
long long rt = 0;
int st = 0;
for(int i=0;i<nums.size();++i){
while(mySet[nums[i]]){
tempSum-=nums[st];
mySet[nums[st]] = false;
++st;
}
tempSum+=nums[i];
mySet[nums[i]] = true;
if(i-st+1>=k){
rt = max(rt,tempSum);
tempSum-=nums[st];
mySet[nums[st]] = false;
++st;
}
}
return rt;
}
};这时候就成了双百。
第九题：1423. 可获得的最大点数 - 力扣（LeetCode）
这道题如果没有做过类似的，那么其实很困难的。
但是如果别人一点，那么就变成了滑动窗口简单题。
使用逆向思维！！！
-
逆向思维：问题要求从卡片中选取
k张卡片，使得得分最大。逆向思维的做法是：我们可以先计算总和sum，然后求解从剩余的n-k张卡片中选择的最小和。最后，最大得分就是总和减去这n-k张卡片的最小和。 -
滑动窗口：使用滑动窗口来计算选择
n-k张卡片的最小和。通过维护一个固定大小为n-k的窗口，滑动窗口计算每一段的和，并更新最小和ret。最终返回sum - ret，即最大得分。
class Solution {
public:
int maxScore(vector<int>& cardPoints, int k) {
// 逆向思维
int n=cardPoints.size();
// 拿n-k个，使得和最小
int ret=INT_MAX;
int sum=0;
for(auto& e:cardPoints) sum+=e;
if(n==k) return sum;
for(int left=0,right=0,sum1=0;right<n;right++)
{
sum1+=cardPoints[right];
if(right-left+1>=n-k)
{
ret=min(ret,sum1);
sum1-=cardPoints[left++];
}
}
return sum-ret;
}
};总结
总的来说灵神的定长滑动窗口的基础题一共18道题。其中5道是会员题。剩下的13道题我在一刷的时候也是可以自己完成10道，也只有3道没有写出来（本文章展示了九道，其中一道优化没有想出来，就不写了）。所以定长滑动窗口难度不是很大。动动脑子想一想就出来了。
更多推荐
19
0- 0
已为社区贡献2条内容
所有评论(0)