209.长度最小的子数组

一、问题描述

题目

给定一个含有 n 个正整数的数组和一个正整数 s，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的子数组，返回 0。

示例

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

提示

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= s <= 109

二、方案一：暴力法

1、思路

暴力法是最直接的方法。我们遍历数组中的每个可能的子数组，计算它们的和，然后找到满足条件的最短子数组。

2、代码实现

func minSubArrayLen(s int, nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    minLen := math.MaxInt32
    for i := 0; i < n; i++ {
        sum := 0
        for j := i; j < n; j++ {
            sum += nums[j]
            if sum >= s {
                if j - i + 1 < minLen {
                    minLen = j - i + 1
                }
                break
            }
        }
    }
    if minLen == math.MaxInt32 {
        return 0
    }
    return minLen
}

3、复杂度分析

• 时间复杂度：O(n^2)，其中 n 是数组的长度。最坏情况下，我们需要遍历每个元素作为子数组的起始位置。
• 空间复杂度：O(1)，只使用了常数个额外空间。

三、方案二：滑动窗口

1、思路

滑动窗口是解决这类问题的更高效方法。我们维护一个窗口，窗口的和大于等于s时，尝试缩小窗口大小；小于s时，增加窗口大小。

2、代码实现

func minSubArrayLen(s int, nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    minLen := math.MaxInt32
    left, sum := 0, 0
    for right := 0; right < n; right++ {
        sum += nums[right]
        for sum >= s {
            if right - left + 1 < minLen {
                minLen = right - left + 1
            }
            sum -= nums[left]
            left++
        }
    }
    if minLen == math.MaxInt32 {
        return 0
    }
    return minLen
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。每个元素最多被访问两次。
• 空间复杂度：O(1)，只使用了常数个额外空间。

四、总结

方案	时间复杂度	空间复杂度	优点	缺点
暴力法	O(n^2)	O(1)	实现简单	效率低，不适合大数据集
滑动窗口	O(n)	O(1)	高效	实现相对复杂

在大多数情况下，推荐使用滑动窗口方法，因为它在处理大数据集时更为高效。