LC209. 长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。 示例 1： 输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。 示例 2： 输入：target = 4, nums = [1,4,4] 输出：1 示例 3： 输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0 提示： 1 <= target <= 109 1 <= nums.length <= 105 1 <= nums[i] <= 105 进阶： 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

题目解析

题目在说什么

题目给了你一个全是正整数的数组，比如 [2,3,1,2,4,3]，还有一个目标值 target=7。你要在数组里找一段连续的、挨在一起的子数组（不能跳着选），让这段子数组里所有数的和大于等于 target。而且，这段子数组要尽可能短，最后返回它的长度。如果整个数组加起来都达不到 target，就返回 0。

举个例子：[2,3,1,2,4,3] 里，[4,3] 的和是 7，长度是 2，没有更短的子数组能到 7 了，所以答案是 2。

思路是怎么来的

想象一下，你有一排积木，每个积木上写着一个数字。你想找一小段连续的积木，让它们的数字加起来至少是 7。你会怎么找？

最笨的办法是：从第一个积木开始，一个一个往后加，直到和超过 7，记下这段的长度；然后从第二个积木开始，再重复……这样虽然能找到答案，但太慢了，数组一大就不行。

聪明一点的办法是：用两个手指头，一个叫左手指（left），一个叫右手指（right），它们之间夹着的就是当前考虑的一段子数组。一开始，两个手指都放在最左边。然后，右手指慢慢往右移动，每移动一次，就把新碰到的数字加到当前和里。一旦当前和超过了 target，就说明找到了一个候选子数组。这时候，左手指开始往右移动，试图缩短这段子数组，同时保持和依然大于等于 target。每移动一次左手指，就更新一下最短长度。如果左手指移动后和变小了、不够 target 了，就停下来，让右手指继续往右移动，扩大范围。

这个过程就像用一把可以伸缩的尺子，先拉长到够长，再试着缩短，找到最短的刚好够长的长度。因为每个元素只被左手指和右手指各碰一次，所以速度很快。

代码逐步拆解

我们来看参考代码，一行一行解释。

int left = 0;          // 左手指，初始在最左边
int sum = 0;           // 当前子数组的和
int result = nums.length + 1;  // 先设一个很大的数，比如数组长度+1，用来记录最短长度

• left 是滑动窗口的左边界，一开始在 0 位置。
• sum 用来记录当前 left 到 right 之间所有数的和。
• result 初始化为一个比数组长度还大的数（比如数组长度是 8，就设成 9）。这样如果最后 result 还是 9，就说明没找到符合条件的子数组，返回 0。

for (int right = 0; right < nums.length; right++) {
    sum += nums[right];   // 右手指往右移动，把新数字加到和里

• right 是右边界，从 0 开始，每次循环右移一位。
• 每移动一次，就把 nums[right] 加到 sum 里，表示当前子数组变长了。

    while (sum >= target) {
        result = Math.min(result, right - left + 1);  // 更新最短长度
        sum -= nums[left];   // 把左手指指的数字从和中移除
        left++;              // 左手指向右移动，缩短子数组
    }
}

• 一旦 sum 大于等于 target，说明当前子数组满足条件。我们就用 right - left + 1 算出它的长度，和之前保存的 result 比较，取较小的那个。