每天(?)一道Leetcode(18) Minimum Size Subarray Sum

Array

209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

即 求子数组之和大于等于给定值的最小长度
要求实现O(n)和O(logn)两种算法

1. 先看O(n)：
   利用指针实现,用来记录子数组的左端点
   当前指针位置开始遍历数组，当子数组之和大于等于给定数值或移动到数组最后时，更新最短距离
   并将左端点右移一位，sum中减去原左端点值

class Solution:
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        right = 0
        sums = 0
        res = len(nums) + 1
        for i in range(len(nums)):
            sums += nums[i]
            while sums >= s:
                res = min(res,i-right+1)
                sums -= nums[right]
                right += 1
        
        return res if res <= len(nums) else 0

2. O(logn)
   利用binary search
   明天更