连续六天的新增订单数是 [2, 3, 1, 2, 4, 3]。现在想找一段连续的日期,让订单总数至少达到 7,而且这段时间尽可能短。
前四天 [2, 3, 1, 2] 总计 8,满足要求,长度为 4;最后两天 [4, 3] 总计 7,长度只有 2。因为单独一天都不足 7,所以最终答案是 2。
这一篇通过这个问题学习滑动窗口:保存一个连续区间,让它的左右边界向前移动。代码使用 Java 17+;系列目录包含完整学习顺序,上一篇是哈希表与两数之和。
一、先确认“连续”和输入条件
题目输入是一个所有元素都大于零的整数数组,以及一个大于零的目标值。输出满足区间和至少为目标值的最短长度;不存在这样的区间时返回 0。
连续意味着不能跳着选。数组 [2, 3, 1, 2, 4, 3] 中,[1, 2, 4] 是连续子数组,而从第一天和第五天各选一个数字,就不属于这里的候选区间。
| 输入 | 目标 | 答案 | 解释 |
|---|---|---|---|
[2, 3, 1, 2, 4, 3] | 7 | 2 | 最后两个元素达标 |
[1, 7, 2] | 7 | 1 | 单个元素 7 已经达标 |
[1, 2, 3] | 20 | 0 | 整个数组都不够 |
[] | 7 | 0 | 不存在非空区间 |
“全为正数”会决定边界能否只向前移动。后面会用一个含负数的例子,说明失去这个条件时为什么不能直接套用。
二、先从枚举起点和终点开始
最容易想到的办法是:固定起点,逐个尝试后面的终点,同时累加区间和。下面展示核心循环,假设已经检查过输入:
int best = values.length + 1;for (int left = 0; left < values.length; left++) { long sum = 0; for (int right = left; right < values.length; right++) { sum += values[right]; if (sum >= target) { best = Math.min(best, right - left + 1); break; } }}return best == values.length + 1 ? 0 : best;固定起点后,第一次达标的终点已经给出该起点下的最短区间,所以可以结束内层循环。即使如此,如果目标很大、一直无法达标,仍要尝试接近 n(n + 1) / 2 个区间,最坏时间是 O(n²)。
这里已经把累加保留在内层循环里。如果每次选出一个区间,都再用第三层循环从头求和,最坏还会增加到 O(n³)。
下一步改进的关键在于:起点向右挪一个位置时,可以从已有区间和里减去离开的数字,无须重新计算整个区间。
三、左右边界怎样移动
用 left 和 right 表示当前窗口的左右下标,两端都包含在区间里。因此,窗口长度为 right - left + 1。
这两个下标也叫“双指针”。在这里它们只是数组位置,不需要学习底层内存地址。滑动窗口是双指针的一种用法:两个边界共同描述一段连续数据,并维护这段数据的状态。
我们维护三个变量:left 是左边界,sum 是窗口内元素之和,best 是目前找到的最短长度。处理流程是:
- 右边界加入一个新元素,把它加到
sum。 - 如果总和还不够,继续扩大右边界。
- 如果总和已经达标,记录当前长度,再移除左端元素,尝试缩短窗口。
- 只要缩短后仍达标,就继续缩短;不足时,再等待右边界加入新元素。
第三步必须反复尝试,所以代码里使用 while,而不是只执行一次的 if。
四、把整个移动过程列出来
仍然使用 [2, 3, 1, 2, 4, 3],目标为 7。初始 left = 0、sum = 0,还没有找到答案。
| 新加入的右下标 | 加入后的总和 | 本轮检查到的达标窗口 | 收缩结束后 |
|---|---|---|---|
| 0,加入 2 | 2 | 无 | left=0,sum=2 |
| 1,加入 3 | 5 | 无 | left=0,sum=5 |
| 2,加入 1 | 6 | 无 | left=0,sum=6 |
| 3,加入 2 | 8 | [0,3],长度 4 | left=1,sum=6 |
| 4,加入 4 | 10 | [1,4] 长度 4;[2,4] 长度 3 | left=3,sum=6 |
| 5,加入 3 | 9 | [3,5] 长度 3;[4,5] 长度 2 | left=5,sum=3 |
表中的 [1,4] 表示下标区间,不是两个元素组成的数组。
重点看倒数第二行:加入 4 后,总和为 10。先记录长度 4,减去左端的 3 后总和为 7,仍达标,再记录长度 3。继续减去左端的 1,总和变成 6,这才停止收缩。
过程中始终保持:sum 等于当前闭区间 [left, right] 的元素之和;当区间缩成空区间时,总和为零。更新边界和更新总和必须同步进行。
五、为什么这样移动不会漏掉更短答案
所有数字都为正数,因此右边加入数字,总和只会增大;左边移除数字,总和只会减小。这种变化方向明确的性质,让我们能够决定下一步。
当窗口不足时,继续收缩只会让总和更小,需要扩张右边界。达标时则尽量收缩,为当前右端点寻找更短的答案。
一旦某个起点已经产生过达标区间并被移除,之后再把右边界往后扩张,用这个旧起点得到的区间只会更长。因此,为寻找全局最短长度,没有必要退回那个起点重新尝试。
这也是阅读双指针代码时应该追问的事情:某个位置被跳过以后,为什么再也不需要访问它?只有移动规则有依据,代码中的两个下标才构成可靠的算法。
六、Java 实现与运行
下面展示完整方法,可放入 SlidingWindow 类中。含 main 的文件见 SlidingWindow.java,也可下载系列全部源码。
public static int minLength(int[] values, long target) { if (values == null || target <= 0) { throw new IllegalArgumentException("array required; target must be positive"); } for (int value : values) { if (value <= 0) { throw new IllegalArgumentException("all values must be positive"); } } int left = 0; int best = values.length + 1; long sum = 0; for (int right = 0; right < values.length; right++) { sum += values[right]; while (sum >= target) { best = Math.min(best, right - left + 1); sum -= values[left]; left++; } } return best == values.length + 1 ? 0 : best;}数组元素是 int,累计总和使用 long,避免多个较大正整数相加时超出 int 范围。best 初始为比数组长度更大的值,表示尚未找到答案;如果一直没有更新,最后转换成约定的 0。
这份实现显式拒绝零和负数,以保持本篇输入约定清楚。检查输入需要一次遍历,也计入整体时间,但不会改变线性增长的结论。
把下载文件保存在本地,进入文件所在目录运行:
javac -encoding UTF-8 SlidingWindow.javajava SlidingWindow预期输出:
20分别对应本文主例子和总和不足的例子。
七、有两层循环,为什么仍是 O(n)
外层 for 让 right 从头走到尾,移动 n 次。内层 while 看起来嵌套在里面,但 left 不会每轮回到零:它在整个方法执行过程中也只会向前移动,最多 n 次。
因此,每个元素最多被加入一次、移除一次,总工作量与 n 成正比,时间复杂度为 O(n)。这个判断来自累计移动次数,而不是循环写了几层。
算法没有复制窗口,也没有额外建立数组,只保存几个变量,所以额外空间是 O(1)。
负数为什么会破坏这个规则
假设输入变成 [1, -1, 3],目标为 3。真实答案是最后一个元素 [3],长度为 1。
如果跳过输入检查,直接套用上面的窗口逻辑,读到末尾时总和为 3,记录长度 3;接着移除左边的 1,总和降为 2,算法便停止收缩。然而,如果再移除 -1,总和反而会回到 3,从而得到更短答案。
负数让“移除左端元素,总和只会减小”不再成立。因此,看到连续区间问题时,要先检查数字和条件的性质,再决定是否使用滑动窗口。允许负数的版本需要其他思路,不能只删掉检查代码就认为完成了扩展。
八、练习:固定长度的最大区间和
把问题改成:给定数组和长度 k,求所有长度恰好为 k 的连续区间中的最大总和。约定 1 <= k <= 数组长度。
例如 [2, 3, 1, 2, 4, 3]、k = 3,候选总和依次为 6、6、7、9,答案为 9。
提示:先算前 k 项之和,然后每向右移动一步,加上新进入的元素,减去刚离开的元素。这里窗口长度固定,不需要按总和决定是否收缩,因此数组包含负数也能使用这套更新方式。
再用 [-5, -2, -8]、k = 2 验证,答案应为 -7。最大值初始化时应使用第一个真实窗口的总和,不能直接设为 0。这会呼应第一篇里“全是负数时怎样找最大值”的边界问题。
下一篇学习二分查找,继续练习有依据地缩小搜索范围:当数组已经有序时,怎样一次排除一半候选位置。
If this article helped you, please share it with others!
Some information may be outdated






