原题:https://leetcode.cn/problems/minimum-size-subarray-sum
问题
给定一个含有 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
解法
子数组可以看做一段数组区间,题目要求这段区间的和大于等于指定值,那么使用滑动窗口的思路,让滑动窗口内的子数组的和大于等于 target,比较得到最小长度,从头到尾一直滑到 nums 末尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 查找数组 nums 中,其和大于等于 target 的连续子数组的最小长度,如果没有那么返回0
func minSubArrayLen(target int, nums []int) int {
if len(nums) == 0 {
return 0
}
// 最大子数组长度为 len(nums),将结果设为最大值+1
result := len(nums) + 1
var start, end = 0, 0
var sum = 0
for end <= len(nums)-1 {
sum = sum + nums[end]
for sum >= target {
// 比较出一个小的 result
if result > end-start+1 {
result = end - start + 1
}
// sum 缩小,然后再继续比较
sum = sum - nums[start]
start++
}
end++
}
if result > len(nums) {
return 0
}
return result
}
func main() {
var a1 = []int{3, 6, 2, 1, 8, 7, 0}
// 2
fmt.Println(minSubArrayLen(10, a1))
var a2 = []int{3, 6, 2, 1, 8, 7, 0}
// 0
fmt.Println(minSubArrayLen(100, a2))
}