网站建设 联系我们四年级摘抄一小段新闻
滑动窗口（1）
滑动窗口是一种基于双指针的思想，两个指针指向的元素形成一个窗口。一般用于求取数组或字符串的某个子串、子序列、最长最短等最值或者求某个目标值时，并且该问题本身可以通过暴力解决。
滑动窗口分为固定窗口和不定窗口。固定窗口就是左右边界都是固定的一起移动。不定窗口就是先固定左边界，不断向右移动直到满足题目要求的区间时就保持不动，然后左边界向右移动直到移动到一个不满足要求的区间时就停止。
常见题目分析（天赐细莲博客）：
存在一个指定序列
是否指定子序列长度
确定长度，固定窗口
不确定长度，但有范围，不定长窗口
需要对子序列进行访问和操作
只有当我们处理完所有子序列时才能保证获得最终答案
这些题目通常都比较模板，不同点往往在于 不同题对子序列的不同处理需求
固定窗口型是不定长窗口型的学习基础，当然思路和实现也比较简单
举个例子
在字符串“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到达字符串的尽头。