【算法】滑动窗口三步走 (2)

当窗口的和恰好等于 target 的时候,我们需要记录此时的结果。设此时的窗口为 \([i, j)\),那么我们已经找到了一个 i 开头的序列,也是唯一一个 i 开头的序列,接下来需要找 i+1 开头的序列,所以窗口的左边界要向右移动

对于第二个问题,我们可以稍微简单地证明一下:

【算法】滑动窗口三步走

我们一开始要找的是 1 开头的序列,只要窗口的和小于 target,窗口的右边界会一直向右移动。假设 \(1+2+\dots+8\) 小于 target,再加上一个 9 之后, 发现 \(1+2+\dots+8+9\) 又大于 target 了。这说明 1 开头的序列找不到解。此时滑动窗口的最右元素是 9。

接下来,我们需要找 2 开头的序列,我们发现,\(2 + \dots + 8 < 1 + 2 + \dots + 8 < \mathrm{target}\)。这说明 2 开头的序列至少要加到 9。那么,我们只需要把原先 1~9 的滑动窗口的左边界向右移动,变成 2~9 的滑动窗口,然后继续寻找。而右边界完全不需要向左移动。

以此类推,滑动窗口的左右边界都不需要向左移动,所以这道题用滑动窗口一定可以得到所有的解。时间复杂度是 \(O(n)\)

注:这道题当前可以用等差数列的求和公式来计算滑动窗口的和。不过我这里没有使用求和公式,是为了展示更通用的解题思路。实际上,把题目中的正整数序列换成任意的递增整数序列,这个方法都可以解。

适用场景

适用于需要以某一窗口范围的元素遍历数组,而不是单个遍历每个元素。

关键词:窗口、范围

滑动窗口三步走

设滑动窗口的左边界为 i,右边界为 j,则滑动窗口框起来的是一个左闭右开区间 \([i, j)\)
滑动窗口前闭后开,也没想象的那么复杂,其实就是一个队列啦!我们写滑动窗口,其实就是手动实现一个队列啦!!!
详情请看:【数据结构】栈与队列

注意,为了编程的方便,滑动窗口一般表示成一个左闭右开区间。在一开始,\(i=1, j=1\),滑动窗口位于序列的最左侧,窗口大小为零

滑动窗口只有 右边界向右移动(扩大窗口)左边界向右移动(缩小窗口) 两个操作,所以实际上非常简单。

特征:

前闭后开,left 元素包含在滑动窗口内,right 元素不包含在滑动窗口内

使用 right 来进行遍历元素,满足条件就 right++,加入滑动窗口

滑动窗口 left、right 只能前进,不能后退,所以一般只用比较最大值即可

操作:

右边界向右移动(扩大窗口):(双指针)right++; 或者 (双端队列)linkedList.addFirst(right);

左边界向右移动(缩小窗口):(双指针)left++; 或者 (双端队列)linkedList.removeLast();

滑动窗口三步走:

1. 明确循环条件

1.明确循环条件:right 如何遍历数组?什么时候保持循环,什么时候结束循环?

注意:由于滑动窗口是利用队列的原理实现的,前闭后开,所以你得思考一下循环的条件是right < s.length()还是right <= s.length()?
因为有时候使用 right 来一个一个遍历元素时,我们right < s.length()即可遍历完所有元素;
如果我们有时候不使用 right 来一个一个遍历元素的话,即 right 只充当边界使用,那我们就需要right <= s.length()才能遍历完所有元素,这里需要特别注意了!!!切勿生搬硬套!

2. 寻找扩缩条件

2.寻找扩缩条件:窗口何时扩大,何时缩小?

注意:这个扩大与缩小的时机得根据题意来具体情况具体分析,并没有一个详细的标准。

3. 完成目标功能

3.完成目标功能:当滑动窗口满足条件时,完成目标功能。

滑动窗口法的大体框架

其实,滑动窗口就是通过不断调整子序列的 start 和 end 位置,从而获取满足要求的解。

在介绍滑动窗口的框架时候,大家先从字面理解下:

滑动:说明这个窗口是移动的,也就是移动是按照一定方向来的。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpwyxf.html