详解"/>
滑动窗口模板与实践详解
本篇主要总结关于滑动窗口的相关做题技巧与想关例题。理论部分不会涉及。
滑动窗口模板
1.定义窗口变量——窗口需要维护的变量:数之和,最大最小长度,满足一定条件的元素个数
2.定义窗口,开始滑动——定义左右边界初始化为0,在右边界小于数组长度条件下滑动
3.扩大窗口——添加右边界,更新需要维护的变量
4.收缩窗口(二次更新)—— 在滑动窗口无效或者即将无效的情况下,更新维护的变量,并且收缩滑动窗口的左边界
二次更新的两种情况:
- 滑动窗口的长度是
固定
的!!! 使用if条件
来更新 - 滑动窗口的长度是
可变
的!!! 使用while条件
来更新
5.返回得到答案
代码模板
int func(vector<int>& nums,int k)
{//Step1. 定义维护变量:1. unordered_map<char,int> m; //在需要统计字符或者数字出现的次数的时候,使用哈希表2. int sum=0,res=0; //在需要记录整数数组中的子序列和或者其他求和时,使用sum记录每一次滑动窗口的子和,再利用res得到最大的或者最小的结果 3. int len=0,start=0; //得到字符串的字串,len记录字串长度,start标识字串开始位置//Step2. 确定滑动窗口的边界,开始滑动:int left=0,right=0;while (right< n) // n: 数组长度 {//Step3. 合法更新:每进行一次滑动时,必须要更新的变量:如Step1的哈希表,sum,res,len与start等等......if (满足条件) //满足某一种条件:例如滑动窗口的长度:right-left+1 与某个值相等时,则进行一次判断,保存临时结果{//更新:res=max(res,sum) ......}//Step4: 非法更新//(1): 滑动窗口的长度不固定:使用while来更新窗口while (right-left+1 > m.size())//举个例子:无重复字符的最长字串,你的窗口长度大于哈希表的长度,则一定含有重复元素,因此更新左边界,使用while{.....}//(2): 滑动窗口的长度固定,使用if来更新窗口 if (right>=k-1)//举个例子:子数组的最大平均值,子数组规定长度不能超过k,因此滑窗长度固定{.....}right++;//此处可以改为for循环}return res;//Step5: 返回结果
}
更多推荐
滑动窗口模板与实践详解
发布评论