Minimum Size Subarray Sum

Solution

Complexity

time: $O(n)$
space: $O(1)$

Iterate right

def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    n = len(nums)
    lo = 0
    res = n+1
    curr_sum = 0
    for hi in range(n):
        curr_sum += nums[hi]
        while curr_sum - nums[lo] >= target:
            curr_sum -= nums[lo]
            lo += 1
        if curr_sum >= target:
            res = min(res, hi-lo+1)
    return res if curr_sum >= target else 0

Iterate left

def minSubArrayLen(self, s: int, nums: List[int]) -> int:
    n = len(nums)
    csum = 0
    right = 0
    res = sys.maxsize
    for left in range(n):
        while csum < s and right < n:
            csum += nums[right]
            right += 1
        if csum >= s:
            res = min(res, right - left)
        csum -= nums[left]

    if res == sys.maxsize:
        return 0
    else:
        return res