目录
概述
1.定长滑动窗口
思路
复杂度
Code
2.不定长滑动窗口
思路
复杂度
Code
总结
概述
在双指针合集中,我们介绍了双指针算法:
「数组」数组双指针算法合集:二路合并|逆向合并|快慢去重|对撞指针 / LeetCode 88|26|11(C++)
从线性枚举到双指针,我们维护的变量数量从1个提升到2个,那如果我们需要维护一片连续的区域,又该使用什么办法呢?
与双指针算法维护指针指向的两个变量对应的是,滑动窗口也使用双指针,但维护的是两个指针所夹的区间[i,j]。
1.定长滑动窗口
LeetCode 2461:
给你一个整数数组
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 。
思路
所谓维护两指针之间的长度为k的区域,就是利用额外的数据结构储存这段区域的特征。
定长滑动窗口的流程无非是两步:
①展开窗口并创建初始数据结构
②移动窗口并维护过程数据结构
对于本题,我们使用两个数据结构维护区间特征:哈希表和一个单变量sum。不同的题目自有不同的要求。
第一步:先展开窗口到k的大小,我们创建哈希表储存其中数字出现的次数。
当窗口长度达到k时,我们的初始数据结构哈希表也就创建好了。
unordered_map<int,int>cnt;
const int n=nums.size();
long long ans=0,sum=0;
for(int i=0;i<k;i++){cnt[nums[i]]++;sum+=nums[i];
}
if(cnt.size()==k)ans=sum;
一个值得注意的点是,如果哈希表的键值对数量(也就是哈希表的size)正好是k的话,那么这个初始展开的窗口就是有效的,应该令ans=sum,表示我们考虑此为第一种可能得答案。
第二步:窗口开始滑动,哈希表和sum抛出不需再维护的特征。
*注意*:在一轮循环开始是,j位置是窗口右边界(包含j)移动到的位置,因此每轮循环维护的区域是[j-k+1,j]。
抛出j-k,即左边界外的那个位置,当哈希表维护的对应值为0时,我们使用erase彻底将其在哈希表中抹除,以免无效键值对污染哈希表的size。
for(int j=k;j<n;j++){cnt[nums[j-k]]--,cnt[nums[j]]++;if(!cnt[nums[j-k]])cnt.erase(nums[j-k]);sum=sum-nums[j-k]+nums[j];if(cnt.size()==k)ans=max(ans,sum);
}
return ans;
时时更新ans,维护其最大性质。
复杂度
时间复杂度:O(n)
Code
class Solution {
public:long long maximumSubarraySum(vector<int>& nums, int k) {unordered_map<int,int>cnt;const int n=nums.size();long long ans=0,sum=0;for(int i=0;i<k;i++){cnt[nums[i]]++;sum+=nums[i];}if(cnt.size()==k)ans=sum;for(int j=k;j<n;j++){cnt[nums[j-k]]--,cnt[nums[j]]++;if(!cnt[nums[j-k]])cnt.erase(nums[j-k]);sum=sum-nums[j-k]+nums[j];if(cnt.size()==k)ans=max(ans,sum);}return ans;}
};
2.不定长滑动窗口
LeetCode 2958:
给你一个整数数组
nums
和一个整数k
。一个元素
x
在数组中的 频率 指的是它在数组中的出现次数。如果一个数组中所有元素的频率都 小于等于
k
,那么我们称这个数组是 好 数组。请你返回
nums
中 最长好 子数组的长度。子数组 指的是一个数组中一段连续非空的元素序列。
示例 1:
输入:nums = [1,2,3,1,2,3,1,2], k = 2 输出:6 解释:最长好子数组是 [1,2,3,1,2,3] ,值 1 ,2 和 3 在子数组中的频率都没有超过 k = 2 。[2,3,1,2,3,1] 和 [3,1,2,3,1,2] 也是好子数组。 最长好子数组的长度为 6 。
思路
不定长窗口和定长窗口的滑动本质上并无不同,尽管它看起来更难。
仍然,我们使用数据结构维护区间特征,只不过这次,左边界移动的条件是通过访问数据结构来达到的。
具体的,我们会使用外层for循环控制右边界j的移动,而左边界的移动i则有内层while循环来实现。while循环的条件取决于维护[i,j]特征的数据结构,当特征不满足题意时,i左移抛出最左侧特征,并更新数据结构,一直循环到满足题意为止,则我们得到了[i,j]有效窗口区。
不定长滑动窗口的流程可以直接套模板,用伪代码展现的话,应该是这样的:
{
某数据结构 data;
int ans=0;
for(j遍历nums){
data加入nums[j]特征;
while(i<j&&data不满足题设条件)数据结构抛出nums[i],i++;
if(data满足题设条件)更新ans;
}
}
对于本题,数据结构data应为一张记录了元素出现次数的哈希表。
同时,所谓“data不满足题设条件”只需要研究nums[j]即可,因为对于j之前的元素,上一次外层for循环会保证其满足题设条件。
*注意*:更新ans时要确保当前满足题设条件,因为i==j也会退出while循环。
复杂度
时间复杂度:O(n)
复杂度分析:
时间分析: {
指针j共遍历数组一次,复杂度为O(n)。
指针i虽在内层循环,但只前进不倒退,复杂度为O(n)。
故整体复杂度为O(n)。
}
Code
class Solution {
public:int maxSubarrayLength(vector<int>& nums, int k) {unordered_map<int,int>hash;const int n=nums.size();int ans=0;for(int i=0,j=0;j<n;j++){hash[nums[j]]++;while(i<j&&hash[nums[j]]>k)hash[nums[i++]]--;if(hash[nums[j]]<=k)ans=max(ans,j-i+1);}return ans;}
};
总结
滑动窗口是一类经典的双指针问题,它会借用额外的存储结构来维护一段连续的子数组。
但需要注意的是,一旦出现负数,它会变得极其被动,这是由于我们期望滑动窗口维护的区间特征总是右增左减的。