滑动窗口算法

在滑动窗口类型的问题中都会有两个指针，一个用于 延伸 现有窗口的 right 指针，和一个用于 收缩 窗口的 left 指针。在任意时刻，只有一个指针运动，而另一个保持静止。滑动窗口算法的时间复杂度为 ，因为 right 和 left 两个指针都只移动了 n 次。

该算法的大致逻辑如下：

接下来还是看几道典型的 leetcode 题目。

题目描述：

题目分析：

首先想到暴力解法，循环每个子区间，找到满足和大于等于 s 的子区间，更新最小长度。

此时时间复杂度 ，题目提示复杂度应为 ，那需要在常数次遍历中找到答案。在暴力解法中，我们先固定 i ，然后增加 j ，一次结束后，我们将 i 加 1 ，然后再循环 j ，重复的计算主要在这里。那是不是可以保持 j 在上一次循环结束的地方不动呢？我们知道上一次循环结束后 i 和 j 之间的子数组的和大于等于 s ，如果此时 j 不动，然后 i 加 1 ，那我们求得的和就需要减掉 nums[i] ，如果此时的子数组的和满足条件，那最小长度比开始更小了，那我们需要更新最小长度；如果此时子数组的和不满足条件，那我们继续增加 j ，来扩大子数组的长度。这也就是我们的滑动窗口思路。

题目描述：

联系滑动窗口算法，首先我们增大窗口，当条件满足时，缩小窗口。考虑到 t 中可能有重复字符，所以我们的判断条件还需要考虑每个字符的数量一致。

题目描述：

题目分析：

这道题需要关注的窗口为固定长度。我们先不考虑这个点，看看普通的滑动窗口解法：

这个解法中，我们是等到子字符串满足条件了再来缩减窗口。由于题目所述为固定的窗口大小，那我们缩减窗口的条件可以改成如下形式：

题目描述：

和上一题类似，我们还是套用滑动窗口模板：

题目描述：

题目分析：

题目的条件是无重复字符，那我们滑动窗口的条件便是：没有重复字符时，我们增大窗口，出现重复字符时我们缩小滑动窗口。需要注意的是我们更新结果再增加窗口的步骤中。

滑动窗口，顾名思义，就是有一个大小可变的窗口，左右两端方向一致的向前滑动（右端固定，左端滑动；左端固定，右端滑动）。

可以想象成队列，一端在push元素，另一端在pop元素，如下所示：

假设有数组[a b c d e f g h]

一个大小为3的滑动窗口在其上滑动，则有:

1、单层循环

2、双层循环

模板只是一个解题思路，具体的题目可能需要具体分析，但是大体框架是不变的。

记住: 多刷题，多总结，是王道

1、最长不含重复字符的子字符串

2、绝对差不超过限制的最长连续子数组

3、无重复字符的最长子串

4、替换后的最长重复字符

滑动窗口算法就是用以解决数组/字符串的子元素问题

滑动窗口算法可以将嵌套的for循环问题，转换为单循环问题，降低时间复杂度

生命不止坚毅鱼奋斗，有梦想才是有意义的追求

给大家推荐一个免费的学习交流群：

最后，祝大家早日学有所成，拿到满意offer，快速升职加薪，走上人生巅峰。

Java开发交流君样：756584822

像QQ设置这里一样，能够滚动窗口并不影响运行

一句代码搞定！界面需要的控件（分组框，纵向滚动条），代码如下

12345.版本 2.子程序 _纵向滚动条1_位置被改变分组框1.顶边 ＝ －纵向滚动条1.位置

---