0209. Minimum Size Subarray Sum | LeetCode Cookbook

[halfrost]

https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0209.Minimum-Size-Subarray-Sum/

[hanlins]

Follow up里要求O(n logn)的解，可以用前缀和+二分来做:

func minSubArrayLen(target int, nums []int) int {
    sum := make([]int, len(nums) + 1)
    for i, num := range nums {
        sum[i+1] = sum[i] + num
    }
    
    res := len(nums) + 1
    for i := range nums {
        l, r := i+1, len(nums)
        for l < r {
            m := (l + r) / 2
            if sum[m] - sum[i] < target {
                l = m + 1
            } else {
                r = m
            }
        }
        if sum[l] - sum[i] >= target {
            if l-i < res {
                res = l-i
            }
        }
    }
    if res > len(nums) {
        return 0
    }
    return res
}