esc to dismiss

209. 长度最小的子数组

题目

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

解体思路

使用 滑动窗口 算法完成。

暴力解法也可以通过,但耗时较长。

func min(x, y int) int {
    if x > y {
        return y
    }
    return x
}

func minSubArrayLen(target int, nums []int) int {
    start, end := 0, 0
    sum := 0
    arr := math.MaxInt32
    size := len(nums)

    for end < size {
        sum += nums[end]

        for sum >= target {
            arr = min(arr, end - start + 1)
            sum -= nums[start]
            start++
        }

        end++
    }

    if arr == math.MaxInt32 {
        return 0
    }

    return arr
}

经验教训

略。

x