滑动窗口模板与实践详解

详解"/>

滑动窗口模板与实践详解

本篇主要总结关于滑动窗口的相关做题技巧与想关例题。理论部分不会涉及。

滑动窗口模板

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: 返回结果
}