動機

與560不同他可以用sliding window

  • prefix sum + binary search
  • prefix sum in fly + sliding window

Problem

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

 

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]Output: 2Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]Output: 0

 

Constraints:

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

 

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

Sol

內容物只有正數，可以用sliding window

class Solution:
    def minSubArrayLen(self, k: int, nums: List[int]) -> int:
        a = 0
        cnt = nums[0]
        ret = float('inf')
        for b,n in enumerate(nums[1:]+[0],1):
            while a<b and cnt >= k:
                ret = min(ret, b-a)
                cnt -= nums[a]
                a += 1
            cnt += n
        return ret if ret != float('inf') else 0

或是，利用prefix sum去找lower bound，這樣符合題目的要求

class Solution:
    def minSubArrayLen(self, k: int, nums: List[int]) -> int:
        sums, cnt, ret = [[0], 0, float('inf')]
        for i in range(len(nums)):
            cnt += nums[i]
            sums.append(cnt)

        for (i,left) in enumerate(sums):
            j = bisect_left(sums,k+left)
            if j < len(sums):
                ret = min(ret, bisect_left(sums,k+left)-i)
        return ret if ret != float('inf') else 0