209. 长度最小的子数组

https://leetcode-cn.com/problems/minimum-size-subarray-sum/

解法一：双指针法

i，j两重循环暴力超时，因此不可取。

left记录左边界，i向右遍历数组，依次累加，当sum>=s时left每次右移一位，并计算最小长度，直到sum<s为止。

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        n = len(nums)
        minSize = n+1    #取一个不能到达的数即可，不一定要sys.maxsize
        left = 0    #左边界
        sum = 0    #left到i的累加和
        for i in range(n):
            sum += nums[i]
            while sum >= s:
                minSize = min(minSize, i-left+1)
                sum -= nums[left]
                left += 1
        #若min还是n+1说明没找到
        return 0 if minSize == n+1 else minSize

解法二：二分

用sums[i]表示序列[0...i-1]的和，因为每个都是正数，因此sums是递增序列，可以用二分（只有这里沾点边，其实这题跟二分没有太大联系），则序列[i...k]的和为sums[k]-sums[i-1]。 思路：每个i（0~n-1）要找一个k，使得sums[k]-sums[i-1] >= target，且要求[i...k]长度最小，因此k尽可能小，即取等号sums[k] = target + sums[i-1]。用二分在sums找对应的k，此时序列长度=k-i+1。每次迭代更新最短长度

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        minLen = n + 1
        sums = [0]
        #计算求和数组sums
        for i in range(0, n):
            sums.append(sums[-1] + nums[i])
        #从1开始遍历sums
        for i in range(1, n+1):
            t = sums[i-1] + target
            #在sums中二分查找t
            pos = bisect.bisect_left(sums, t)    
            if pos != n+1:    #pos为n说明sums中找不到t
                minLen = min(minLen, pos - i + 1)    #更新最短长度
        #minLen仍未n+1说明没找到
        return 0 if minLen == n+1 else minLen