mobile wallpaper 1mobile wallpaper 2mobile wallpaper 3mobile wallpaper 4
2282 words
6 minutes
算法入门(三):双指针与滑动窗口
2026-10-21

连续六天的新增订单数是 [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]72最后两个元素达标
[1, 7, 2]71单个元素 7 已经达标
[1, 2, 3]200整个数组都不够
[]70不存在非空区间

“全为正数”会决定边界能否只向前移动。后面会用一个含负数的例子,说明失去这个条件时为什么不能直接套用。

二、先从枚举起点和终点开始#

最容易想到的办法是:固定起点,逐个尝试后面的终点,同时累加区间和。下面展示核心循环,假设已经检查过输入:

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 是目前找到的最短长度。处理流程是:

  1. 右边界加入一个新元素,把它加到 sum。
  2. 如果总和还不够,继续扩大右边界。
  3. 如果总和已经达标,记录当前长度,再移除左端元素,尝试缩短窗口。
  4. 只要缩短后仍达标,就继续缩短;不足时,再等待右边界加入新元素。

第三步必须反复尝试,所以代码里使用 while,而不是只执行一次的 if。

四、把整个移动过程列出来#

仍然使用 [2, 3, 1, 2, 4, 3],目标为 7。初始 left = 0、sum = 0,还没有找到答案。

新加入的右下标加入后的总和本轮检查到的达标窗口收缩结束后
0,加入 22无left=0,sum=2
1,加入 35无left=0,sum=5
2,加入 16无left=0,sum=6
3,加入 28[0,3],长度 4left=1,sum=6
4,加入 410[1,4] 长度 4;[2,4] 长度 3left=3,sum=6
5,加入 39[3,5] 长度 3;[4,5] 长度 2left=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.java
java SlidingWindow

预期输出:

2
0

分别对应本文主例子和总和不足的例子。

七、有两层循环,为什么仍是 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。这会呼应第一篇里“全是负数时怎样找最大值”的边界问题。

下一篇学习二分查找,继续练习有依据地缩小搜索范围:当数组已经有序时,怎样一次排除一半候选位置。

Share

If this article helped you, please share it with others!

算法入门(三):双指针与滑动窗口
https://mizuki.mysqil.com/posts/algorithm-03-sliding-window/
Author
梦幻晨风
Published at
2026-10-21
License
CC BY-NC-SA 4.0

Some information may be outdated

Table of Contents