2023/2/12总结

滑动窗口（1）

1. 滑动窗口是一种基于双指针的思想，两个指针指向的元素形成一个窗口。一般用于求取数组或字符串的某个子串、子序列、最长最短等最值或者求某个目标值时，并且该问题本身可以通过暴力解决。

2. 滑动窗口分为固定窗口和不定窗口。固定窗口就是左右边界都是固定的一起移动。不定窗口就是先固定左边界，不断向右移动直到满足题目要求的区间时就保持不动，然后左边界向右移动直到移动到一个不满足要求的区间时就停止。

3. 常见题目分析（天赐细莲博客）：

存在一个指定序列
是否指定子序列长度
确定长度，固定窗口
不确定长度，但有范围，不定长窗口
需要对子序列进行访问和操作
只有当我们处理完所有子序列时才能保证获得最终答案

这些题目通常都比较模板，不同点往往在于 不同题对子序列的不同处理需求
固定窗口型是不定长窗口型的学习基础，当然思路和实现也比较简单

4. 举个例子

在字符串“abbceb"找出最长的不重复的子串，那么我们的做法是这样的：

p,q为指针，ans表示不重复子串的最大值。

a	b	b	c	e	b		ans
p,q							1

a	b	b	c	e	b		ans
p	q						2

a	b	b	c	e	b		ans
p		q					2

a	b	b	c	e	b		ans
		p,q					2

a	b	b	c	e	b		ans
		p	q				2

a	b	b	c	e	b		ans
		p		q			3

a	b	b	c	e	b		ans
					p,q		3

如图，初始化p=q=0,把[p,q]这个区间称为一个窗口。

我们不断地将q往后移动扩宽[p,q]直到窗口中的子串符合要求。然后停止增加q,进行不断地增加p缩小窗口，直到窗口不再符合要求。每次增加p都要更新一轮结果。然后不断的重复这个步骤，直到q到达字符串的尽头。