滑动窗口

滑动窗口用移动的区间寻找满足条件的连续子数组。本课寻找“和至少达到目标的最短子数组”：右端加入元素，达到目标后从左端移除元素，尝试缩短答案。输入元素必须非负，目标必须为正数。时间复杂度为 O(n)，额外空间为 O(1)。

把窗口想成沿数组移动的尺子：先向右扩张，满足条件后再收起左端。两端都只向右移动，不回头重扫。每个元素最多加入一次、移除一次，这是线性时间的来源。

滑动窗口如何工作

维护区间 [left, right] 和窗口和 total。right 从头走到尾，每步先把 nums[right] 加入 total，让窗口向右扩大一格。

只要 total >= target，就先记录当前长度作为候选答案，再从 total 中减去 nums[left]，让 left 右移。移除后仍达标，就继续收缩。窗口和小于目标时，停止收缩，等待右端加入下一个元素。

全程 right 前进 n 次。left 只前进，每个元素最多移除一次，因此也最多前进 n 次。两端合计最多 2n 次移动，不需要检查全部 n(n+1)/2 个连续子数组。播放器的 edges advanced 计数器记录这个总数。

非负条件保证扩张不会减小窗口和，收缩不会增大窗口和。若含负数，移除元素反而可能增大和，停止收缩的判断就可能错过更短答案。

默认输入为 nums = [2, 3, 1, 2, 4, 3]，target = 7。初始 left = 0、total = 0，还没有最佳长度。

right = 0：加入 2，窗口为 [0, 0]，total = 2 < 7，继续扩张。
right = 1：加入 3，窗口为 [0, 1]，total = 5，继续扩张。
right = 2：加入 1，窗口为 [0, 2]，total = 6，继续扩张。
right = 3：加入 2，窗口为 [0, 3]，total = 8，首次达标，记录 best = 4。移除 nums[0] = 2 后，total = 6、left = 1，停止收缩。
right = 4：加入 4，窗口为 [1, 4]，total = 10。长度仍为 4。移除 nums[1] = 3，得到 total = 7、left = 2，窗口 [2, 4] 长度为 3，更新 best = 3。再移除 nums[2] = 1，得到 total = 6、left = 3，停止收缩。
right = 5：加入 3，窗口为 [3, 5]，total = 9。长度为 3，最佳值不变。移除 nums[3] = 2 后，total = 7、left = 4，窗口 [4, 5] 长度为 2，更新 best = 2。再移除 nums[4] = 4，得到 total = 3、left = 5，停止收缩。

右端到达数组末尾，扫描结束。最短答案是下标 4、5 的 [4, 3]，长度为 2。六次扩张加五次收缩，共移动十一回；暴力方法的候选子数组共有 6 · 7 / 2 = 21 个。

动画里的方框表示当前窗口，上方显示窗口和。达到目标时，和的颜色从琥珀色变为绿色。最佳长度依次从 4 降到 3，再降到 2。

本实现即使找到长度 1，也继续扫描剩余输入。两端总移动次数不超过 2n，所以三种情况都是 O(n)。只保存两个下标、窗口和与最佳答案，额外空间为 O(1)。

若允许负数，可以用前缀和与单调双端队列解决同一问题，时间仍为 O(n)，但额外空间为 O(n)，对应 LeetCode #862。固定长度窗口是另一种情况：窗口宽度始终为 k，每步加入一个值、移除一个值，不使用达标后反复收缩的规则。

输入含负数仍套用此规则：对 [3, -2, 5] 和目标 4，算法得到长度 3，但 [5] 的长度 1 已达标。移除 3 后和变成 3，收缩停止，没能继续移除 −2。播放器的含负数场景会展示这个反例。
用 if 代替 while：一次扩张后可能需要连续收缩几次。只移除一个元素，会留下过长窗口。
先收缩再记录长度：记录时窗口必须仍满足条件。先减去 nums[left]，可能会把不达标的窗口记作答案。
让指针后退：如果每次右端移动都把 left 重置为 0，就会重复访问元素，失去 O(n) 的保证。
把变长窗口用于固定宽度任务：固定宽度 k 只需维护进入和离开的元素，不需要判断达标后继续收缩。

这些课程共享同一个技巧，或正好接到下一个概念。

锁标表示交互演示需付费。所有讲解文档均可免费阅读。

发现错误或有不清楚的地方？提交反馈。