0209.minimum-size-subarray-sum

209. 长度最小的子数组

题目描述

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

 

示例：

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

 

进阶：

• 如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

解题思路

定义两个指针 start 和 end 分别表示子数组的开始位置和结束位置，维护变量 sum 存储子数组中的元素和（即从 []nums[start] 到 []nums[end] 的元素和）。

初始状态下，start 和 end 都指向下标 00，sum 的值为 00。

每一轮迭代，将 [end]nums[end] 加到 sum，如果 \ge ssum≥s，则更新子数组的最小长度（此时子数组的长度是 -+1end−start+1），然后将 [start]nums[start] 从 sum 中减去并将 start 右移，直到 sum < s，在此过程中同样更新子数组的最小长度。在每一轮迭代的最后，将 end 右移。

具体解法

Golang

func minSubArrayLen(s int, nums []int) int {

	if len(nums) == 0 {
		return 0
	}
	ans := math.MaxInt32
	sum := 0
	start := 0

	for end := 0; end < len(nums); end++ {
		sum += nums[end]
		for sum >= s {
			ans = min(end-start+1, ans)
			sum -= nums[start]
			start++
		}
	}
	if ans == math.MaxInt32 {
		return 0
	}
	return ans
}

func min(i, j int) int {
	if i < j {
		return i
	}
	return j
}