滑动窗口

简介：

滑动窗口，顾名思义，就是使用双指针技巧，去维护一个窗口，不断滑动窗口（一端固定，另一端滑动），更新结果，找到最优解。麻烦的不是思路，主要是处理细节问题。

---

适用范围：

多用于解决子序列类的问题。

---

时间复杂度：O(N)

---

思路：

1.初始化left = right = 0，个人习惯区间左闭右开[left,right)，方便处理，这样只要right右移一位，区间[0,1)就包含一个元素了。

2.先不断增加右指针right扩大窗口，直到窗口符合要求。

3.停止增加right，开始不断增加left缩小窗口，直到窗口不再符合要求。同时，每次增加left更新一次结果。

4.重复第2和第3步，直到right到达尽头。

思路就是第2步寻找可行解，第3步对可行解进行优化，最终找到最优解。

---

//初始化左右指针
int letf = 0, right = 0;
while(right < str.size()){
	//c是将要移入窗口的字符
	char c = str[right];
	//增大窗口
	right++;
    
    //更新散列表或数组中数据
    
	while(/*左侧窗口需要收缩*/){
		//h是将要移出窗口的字符
		char h = str[left];
		//缩小窗口
		left++;
        
        //更新散列表或数组中数据
        
	}
}