广州网站开发债券交,资兴市住房和城乡建设局网站,百度网站上传,想学网页设计报考什么专业目录
概述
1.定长滑动窗口
思路
复杂度
Code
2.不定长滑动窗口
思路
复杂度
Code
总结 概述
在双指针合集中#xff0c;我们介绍了双指针算法#xff1a;
「数组」数组双指针算法合集#xff1a;二路合并|逆向合并|快慢去重|对撞指针 / LeetCode 88|26|11#…目录
概述
1.定长滑动窗口
思路
复杂度
Code
2.不定长滑动窗口
思路
复杂度
Code
总结 概述
在双指针合集中我们介绍了双指针算法
「数组」数组双指针算法合集二路合并|逆向合并|快慢去重|对撞指针 / LeetCode 88|26|11C
从线性枚举到双指针我们维护的变量数量从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_mapint,intcnt;
const int nnums.size();
long long ans0,sum0;
for(int i0;ik;i){cnt[nums[i]];sumnums[i];
}
if(cnt.size()k)anssum;
一个值得注意的点是如果哈希表的键值对数量也就是哈希表的size正好是k的话那么这个初始展开的窗口就是有效的应该令anssum表示我们考虑此为第一种可能得答案。
第二步窗口开始滑动哈希表和sum抛出不需再维护的特征。
*注意*在一轮循环开始是j位置是窗口右边界包含j移动到的位置因此每轮循环维护的区域是[j-k1,j]。
抛出j-k即左边界外的那个位置当哈希表维护的对应值为0时我们使用erase彻底将其在哈希表中抹除以免无效键值对污染哈希表的size。
for(int jk;jn;j){cnt[nums[j-k]]--,cnt[nums[j]];if(!cnt[nums[j-k]])cnt.erase(nums[j-k]);sumsum-nums[j-k]nums[j];if(cnt.size()k)ansmax(ans,sum);
}
return ans;
时时更新ans维护其最大性质。
复杂度 时间复杂度O(n) Code
class Solution {
public:long long maximumSubarraySum(vectorint nums, int k) {unordered_mapint,intcnt;const int nnums.size();long long ans0,sum0;for(int i0;ik;i){cnt[nums[i]];sumnums[i];}if(cnt.size()k)anssum;for(int jk;jn;j){cnt[nums[j-k]]--,cnt[nums[j]];if(!cnt[nums[j-k]])cnt.erase(nums[j-k]);sumsum-nums[j-k]nums[j];if(cnt.size()k)ansmax(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 ans0; for(j遍历nums){ data加入nums[j]特征; while(ijdata不满足题设条件)数据结构抛出nums[i]i; if(data满足题设条件)更新ans; }
}
对于本题数据结构data应为一张记录了元素出现次数的哈希表。
同时所谓“data不满足题设条件”只需要研究nums[j]即可因为对于j之前的元素上一次外层for循环会保证其满足题设条件。
*注意*更新ans时要确保当前满足题设条件因为ij也会退出while循环。
复杂度 时间复杂度O(n) 复杂度分析
时间分析 {
指针j共遍历数组一次复杂度为O(n)。
指针i虽在内层循环但只前进不倒退复杂度为O(n)。
故整体复杂度为O(n)。
}
Code
class Solution {
public:int maxSubarrayLength(vectorint nums, int k) {unordered_mapint,inthash;const int nnums.size();int ans0;for(int i0,j0;jn;j){hash[nums[j]];while(ijhash[nums[j]]k)hash[nums[i]]--;if(hash[nums[j]]k)ansmax(ans,j-i1);}return ans;}
}; 总结
滑动窗口是一类经典的双指针问题它会借用额外的存储结构来维护一段连续的子数组。
但需要注意的是一旦出现负数它会变得极其被动这是由于我们期望滑动窗口维护的区间特征总是右增左减的。
