滑动窗口
简介
滑动窗口算法本质上还是基于左右指针的算法,就是用左右指针规定窗口范围,减少一些不必要的比较,提升算法的时间复杂度。该算法通常用于解决一些子串问题。
注: 子串与子序列不同,子串是要求连续的,子序列不要求连续。子串 == 子数组
框架
1 | //滑动窗口算法框架 |
注:窗口的长度可以用right - left
来表示。
寻找窗口中的元素在子串中
1 | //窗口中添加元素 |
注:valid
指的是满足need要求的元素的个数,这里加减的顺序有所差异,需要注意。
收缩时常用的做法
通常有两种收缩的方式
1.增加窗口时找到了符合题意的字符串,再用缩小窗口来找最优解
2.当出现不可能满足条件时,进行收缩(类似剪枝的感觉),常用的是利用长度来限制right - left > t.size()
,并且在收缩后查看是否满足题意。
注:在寻找多个解时,该框架依然适用,因为本框架增长窗口是一个一个加的,并且每加一个,都会尝试收缩,避免了漏解的可能性。有点像暴力遍历所有解,然后剪枝的感觉。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ae86's Blog!