长度最小的子数组（和 ≥ target）怎么用滑动窗口解？

简化版

在正整数数组里,找和 ≥ target 的最短连续子数组。用求最短滑动窗口:right 扩展窗口、累加窗口和;当窗口和 ≥ target 时,收缩 left 求最短(每收一次更新最小长度、减去移出的值),直到和 < target 再继续扩。O(n)。前提是数组元素非负(否则扩窗口不保证和单调增,滑窗失效,得改用前缀和 + 二分或其它方法)。

详细版

int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0, min = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];                   // 扩展窗口，累加
        while (sum >= target) {               // 窗口和达标 → 收缩求最短
            min = Math.min(min, right - left + 1);
            sum -= nums[left];                // 移出左元素
            left++;
        }
    }
    return min == Integer.MAX_VALUE ? 0 : min;
}

窗口状态:一个变量 sum(窗口内元素和)。
收缩条件:sum >= target——达标就收缩,求最短。
时间 O(n)、空间 O(1)。

完整版教学

一、为什么是「求最短」滑动窗口

题目要「和 ≥ target 的最短子数组」,是求最短滑窗。策略:right 扩展窗口累加和,一旦和 ≥ target(满足条件),就尽量收缩 left 让窗口更短(同时保持和 ≥ target),记录过程中的最小长度。对照模板,属于「满足条件就收缩、收缩时更新 min」。窗口状态简单——只需一个变量 sum 维护窗口和。

二、为什么必须是非负数(核心前提)

滑动窗口能用在这题,依赖一个隐含前提:数组元素非负。因为:

扩展窗口(right++)时,和只会增大或不变(加了个非负数)。
收缩窗口(left++)时,和只会减小或不变(减了个非负数)。

正是这种「和随窗口大小单调变化」的性质,让我们能明确判断「该扩还是该缩」。如果数组有负数,扩窗口可能让和变小、缩窗口可能让和变大,单调性被破坏,滑动窗口就失效了——这时求「和 ≥ target 的最短子数组」要改用前缀和 + 单调队列或前缀和 + 二分等方法。面试常追问「有负数怎么办」,答案就是滑窗不再适用。

三、收缩逻辑:达标后尽量缩

关键在 while (sum >= target):当窗口和达到 target,不是立刻记录就走,而是在保持达标的前提下不断收缩 left,因为更短的窗口如果还能达标,就是更优解。每收缩一次:

先用当前窗口长度 right - left + 1 更新 min。
再移出 nums[left](sum -= nums[left])、left++。
直到 sum < target(不再达标)才退出 while,继续扩 right。

这样每个达标窗口都被收缩到「再缩就不达标」的极限,保证找到最短。

四、走一个例子

target = 7, nums = [2,3,1,2,4,3]
right=0: sum=2
right=1: sum=5
right=2: sum=6
right=3: sum=8 ≥7 → 收缩：min=4([2,3,1,2])，sum=6，left=1，退出
right=4: sum=10 ≥7 → 收缩：min=4→3([3,1,2,4]→len4)... 缩到[2,4]sum=6，min=2? 
        实际：[4,3]在right=5时 sum=7 → min=2
right=5: sum=7 ≥7 → min=2([4,3])
结果 min = 2

五、和「求最长」滑窗的对比

长度最小子数组(求最短):和 ≥ target 就收缩,收缩时更新 min。
无重复最长子串(求最长):不合法才收缩,合法时更新 max。

再次体现滑动窗口两大类的差异:求最短「满足就缩」、求最长「不满足才缩」。这题窗口状态最简单(一个 sum),适合作为「求最短滑窗」的入门。

六、前缀和视角(延伸)

这题也能用前缀和 + 二分:算出前缀和数组(非负数组前缀和递增、有序),对每个右端点 j,二分找最小的 i 使 prefix[j] - prefix[i] >= target。O(n log n),不如滑窗的 O(n),但这个思路能处理一些滑窗处理不了的变体。前缀和和滑动窗口是解「子数组和」问题的两大工具,常配合使用。

七、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：对正数数组，右扩使和不减，左缩使和不增，形成单调窗口。

对应的状态推进是：右端加入后，只要 sum>=target 就记录长度并持续左缩。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。每个元素至多加入和移除一次，O(n)。

带数字走一遍：target=7、[2,3,1,2,4,3] 最短窗口是 [4,3]，长度 2。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	经典滑窗要求元素非负；含负数时单调性失效
时间复杂度	O(n)
额外空间	O(1)
关键边界	答案初值用无穷大；收缩循环中每一步都要更新最短长度
替代方案	含负数可考虑前缀和加单调队列

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“经典滑窗要求元素非负；含负数时单调性失效”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写 O(n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“每个元素至多加入和移除一次，O(n)”。
误区：重复值和边界值不会改变代码。 答案初值用无穷大；收缩循环中每一步都要更新最短长度。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“对正数数组，右扩使和不减，左缩使和不增，形成单调窗口”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“target=7、[2,3,1,2,4,3] 最短窗口是 [4,3]，长度 2”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“含负数可考虑前缀和加单调队列”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

长度最小子数组(和 ≥ target)= 求最短滑动窗口:right 扩展累加 sum,sum >= target 就收缩 left(先更新 min、再减 nums[left])直到不达标,O(n)、O(1)。前提是非负数——非负才保证「扩窗和增、缩窗和减」的单调性;有负数滑窗失效,改用前缀和+二分/单调队列。和「求最长」相反:满足条件就缩、缩时更新 min。

简化版

详细版