209. 长度最小的子数组 #

题目地址 #

解题思路 #

暴力法 #

暴力法是最直观的方法，但是在 leetcode 提交暴力法解题会报「超出时间限制」😴。暴力法可以参看 https://leetcode.cn/problems/minimum-size-subarray-sum/solutions/305704/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/。

初始化子数组的最小长度为无穷大，枚举数组nums中的每个下标作为子数组的开始下标，对于每个开始下标i，需要找到大于或等于i的最小下标j，使得从nums[i]到nums[j]的元素和大于或等于s，并更新子数组的最小长度，此时子数组的长度是 j−i+1。需要注意的是，两个 for 循环都是<len(nums)，不是内层的<len(nums)-1。

滑动窗口法 #

可以参看 B站-长度最小的子数组和 209.长度最小的子数组

具体实现 #

Go滑动窗口

package main

import (
	"fmt"
	"math"
)

func minSubArrayLen02(target int, nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}

	min := func(x, y int) int {
		if x < y {
			return x
		}
		return y
	}

	ans := math.MaxInt32
	i := 0
	sum := 0 // 子数组的和

	for j := 0; j < n; j++ {
		sum += nums[j]
		for sum >= target {
			ans = min(ans, j-i+1)
			sum -= nums[i]
			i++
		}
	}

	if ans == math.MaxInt32 {
		return 0
	}

	return ans
}

func main() {
	fmt.Println(minSubArrayLen02(7, []int{2, 3, 1, 2, 4, 3}))
}

Go暴力法

package main

import (
	"fmt"
	"math"
)

func minSubArrayLen(target int, nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}

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

		return x
	}

	ans := math.MaxInt32
	for i := 0; i < n; i++ {
		sum := 0
		for j := i; j < n; j++ {
			sum += nums[j]
			if sum >= target {
				ans = min(ans, j-i+1)
				break
			}
		}
	}

	if ans == math.MaxInt32 {
		return 0
	}

	return ans
}

func main() {
	fmt.Println(minSubArrayLen(7, []int{2, 3, 1, 2, 4, 3}))
}