209. 长度最小的子数组

[yankewei]

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

示例: 

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

进阶:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum

解答

双指针(滑动窗口)

看到这种求最值且连续的字眼，第一想到的就是滑动窗口。两个指针，把指针之间的数字相加进行判断即可。这里我有两个版本，第一个是未优化的，第二个优化后的版本。

// 未优化的版本，提交之后发现用时仅超过10%，后来仔细看了看，耗时应该是在对指针之间的数字进行计算的过程，其实没有必要在遍历的时候每次重新计算，保存计算的值即可。
func minSubArrayLen(s int, nums []int) int {
    ans := 0
    start, end, length := 0, 0, len(nums)
    for start <= end && end < length {
        // 就在这里每次都对指针之间的数字进行了计算
	sum := sliceSum(nums, start, end)
	if sum >= s {
	    c := end - start + 1
	    if ans == 0 || c < ans {
		ans = c
	    }
	    start++
	} else {
	    end++
	}
    }
    return ans
}

func sliceSum(s []int, start int, end int) int {
    ans := 0
    for start <= end {
	ans += s[start]
	start++
    }
    return ans
}

// 优化后
func minSubArrayLen(s int, nums []int) int {
    length := len(nums)
    if length == 0 {
        return 0
    }
    ans := 0
    start, end, sum, length := 0, 0, nums[0], len(nums)
    for {
	if sum >= s {
	    c := end - start + 1
	    if ans == 0 || c < ans {
	        ans = c
	    }
	    sum -= nums[start]
	    start++
	} else {
	    end++
	    if end >= length {
		break
	    }
	    sum += nums[end]
	}
    }
    return ans
}