题目特征

滑动窗口类算法因其所具有的独特算法特征，因此需要用到滑动窗口解决的算法一般在题目中都有明显的特征，可以从题目中的关键字看出来。 一般这些题目的特征可归纳为： 求满足XXX条件（一般这些条件为满足什么样的计算结果、出现多少次、不包含重复字符、包含XXX等条件） 最长/最短 子串、子序数、子数组这些子数组、子序列等都是连续的 题目中出现上述关键词时，一定要想到用滑动窗口算法求解。 滑动窗口的优点是可以将嵌套循环问转化为单循环问题，降低循环复杂度

解题思路

首先在滑动窗口类问题中需先声明四个变量：标志窗口两端的左右指针left & right、记录当前结果的result以及记录最优结果的bestresult。 滑动窗口算法是单循环，循环的终止条件为窗口右指针滑动到容器（传进算法中的字符串、数组、链表等容器）结尾； 在循环中进行右端窗口扩大（右指针右移滑动）并更新当前结果result，判断若result优于bestresult则更新bestresult。当满足或者违反题目给出的某一条件时，左窗口右滑收缩。 最终返回bestresult即可

求longest子序列的算法模板可如下所示：

int sliding_window_template(容器)
{
          
   
	int left = right = 0;//初始化左右端窗口
	int result,bestresult;//初始化当前结果以及最优结果
	while(右指针未滑动到结尾)
	{
          
   
		右端窗口右滑，并且更新result
		while(违反题目条件)
		{
          
   
			左窗口右滑，收缩窗口，更新result
		}
		if(result优于bestresult)		
		{
          
   
			更新bestresult
		}
	}
	return bestresult;
}

求shortest的算法模板

int sliding_window_template(容器)
{
          
   
	int left = right = 0;//初始化左右端窗口
	int result,bestresult;//初始化当前结果以及最优结果
	while(右指针未滑动到结尾)
	{
          
   
		右端窗口右滑
		while(满足题目条件)
		{
          
   
			左窗口右滑，收缩窗口，更新result
		}
		if(result优于bestresult)		
		{
          
   
			更新bestresult
		}
	}
	return bestresult;
}

经典案例