209. 长度最小的子数组 Medium

给定一个含有 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

解题思路

输入：一个正整数数组 nums 和一个正整数 target

输出：找出总和大于等于 target 的最短连续子数组长度，如果不存在则返回 0

本题属于可变长度滑动窗口问题。

我们使用双指针（left 和 right）来维护一个滑动窗口，并通过变量记录窗口内的元素总和。每次右指针向右移动时，将当前元素加入窗口总和；当总和大于等于 target 时，说明当前窗口是一个合法解，此时尝试不断移动左指针缩小窗口，以寻找更短的合法子数组，并更新最小长度。

整个过程中动态调整窗口大小，并在每次满足条件时更新最小值。最终返回记录的最小长度，如果没有满足条件的窗口，则返回 0。

代码实现

python

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0                      # 滑动窗口左边界
        n = len(nums)
        min_len = float('inf')       # 初始化最小长度为无穷大
        window_sum = 0               # 当前窗口内元素的和

        for right in range(n):
            window_sum += nums[right]  # 扩大窗口，加入右端元素

            # 当窗口内元素和大于等于目标值，开始收缩左边界
            while window_sum >= target:
                min_len = min(min_len, right - left + 1)  # 更新最小长度
                window_sum -= nums[left]  # 移除左端元素
                left += 1                # 左指针右移，缩小窗口

        # 如果没找到符合条件的子数组，返回 0
        return 0 if min_len == float('inf') else min_len

javascript

const minSubArrayLen = function(target, nums) {
    let left = 0;
    let minLen = Infinity;
    let windowSum = 0;

    for (let right in nums) {
        windowSum += nums[right];
        while (windowSum >= target) {
            minLen = Math.min(minLen, right - left + 1)
            windowSum -= nums[left];
            left += 1;
        }
    }

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

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

209 国际版

209 中文版