#209. 长度最小的子数组

LeetCode 原题链接

#题目描述

给定一个含有 n 个正整数的数组和一个正整数 target。

找出该数组中满足其总和大于等于 target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。

如果不存在符合条件的子数组，返回 0。

示例：

输入: target = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的子数组。

输入: target = 4, nums = [1,4,4]
输出: 1

输入: target = 11, nums = [1,1,1,1,1,1,1,1]
输出: 0

#1. 题型判断

本题要求找到满足和大于等于 target 的最短连续子数组。

关键词是“连续子数组”和“最短长度”，所以优先考虑滑动窗口。

并且题目给出的 nums 都是正整数，这一点非常关键：

• 当右边界 right 向右移动时，窗口和只会增加。
• 当左边界 left 向右移动时，窗口和只会减少。

因此窗口状态具有单调性，可以通过不断扩大和收缩窗口找到最短合法长度。

#2. 指针含义

使用闭区间窗口 [left, right]。

• left：当前窗口左边界。
• right：当前窗口右边界，也是正在加入窗口的新元素下标。
• sum：当前窗口 [left, right] 内所有元素的和。
• ans：目前找到的最短合法子数组长度。

窗口 [left, right] 表示当前正在检查的一段连续子数组。

#3. 窗口或区间维护规则

每次 right 向右移动时，把 nums[right] 加入 sum，表示窗口向右扩大：

sum += nums[right];

如果此时 sum >= target，说明当前窗口已经满足条件。

但本题要求最短长度，所以不能立刻停止，而是要继续尝试移动 left 缩小窗口：

while (sum >= target) {
  ans = Math.min(ans, right - left + 1);
  sum -= nums[left];
  left++;
}

每次 left 右移之前，都要先从 sum 中减去 nums[left]，因为它即将离开窗口。

#4. 答案更新时机

本题求的是最短合法窗口。

只要 sum >= target，当前窗口 [left, right] 就是一个合法候选答案，此时先更新答案：

ans = Math.min(ans, right - left + 1);

然后再移动 left，尝试找到更短的合法窗口。

这里必须使用 while，而不是 if。因为移除一个左侧元素后，窗口可能仍然满足 sum >= target，此时还可以继续缩短。

例如：

target = 7, nums = [2,3,1,2,4,3]

当窗口扩展到 [2,3,1,2] 时，和为 8，满足条件。移除左侧的 2 后，窗口变成 [3,1,2]，和为 6，不满足条件。

后面扩展到 [3,1,2,4] 时，和为 10，需要连续收缩，才能发现更短的 [4,3]。

#5. 边界条件与易错点

边界条件：

• 如果没有任何子数组满足 sum >= target，最终返回 0。
• 如果某个单独元素已经大于等于 target，最短长度就是 1。
• 如果整个数组之和仍然小于 target，返回 0。

易错点：

不要在每次移动 right 时重新遍历 [left, right] 来计算窗口和。

错误示例：

for (let right = 0; right < nums.length; right++) {
  for (let j = left; j < right; j++) {
    sum += nums[j];
  }
}

这种写法有两个问题：

• sum 没有清零，会重复累加之前窗口里的元素。
• 内层循环 j < right 没有把 nums[right] 加进去，但后面又按照 right - left + 1 计算长度，窗口范围和窗口和不一致。

滑动窗口的核心是增量维护状态：

• right 每右移一次，只加入一个新元素 nums[right]。
• left 每右移一次，只移除一个旧元素 nums[left]。

这样才能保证每个元素最多进窗口一次、出窗口一次。

#6. 代码实现

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
  let ans = Infinity;
  let sum = 0;
  let left = 0;

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];

    while (sum >= target) {
      ans = Math.min(ans, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }

  return ans === Infinity ? 0 : ans;
};

#7. 复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度。right 从左到右遍历一次，left 也只会向右移动，不会回退。
• 空间复杂度：O(1)，只使用了 ans、sum、left 等常数级变量。