209.-minimum-size-subarray-sum.md

209. Minimum Size Subarray Sum

• Medium
• 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.

Analysis

This is another example of using sliding window. Whenever we add an number into the list, we remove some from the front and make sure the window we are using remains the smallest possible with these values.

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        i=0
        mini=float('inf')
        for j in range(len(nums)):
            target-=nums[j]
            while target<=0:
                mini=min(mini,j-i+1)
                target+=nums[i]
                i+=1

        if mini==float('inf'):
            return 0
        else:
            return mini

There is another same solution. Just changing from subtracting to adding

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        i=0
        sumi=0
        mini=float('inf')
        for j in range(len(nums)):
            sumi+=nums[j]
            while sumi>=target:
                mini=min(j-i+1,mini)
                sumi-=nums[i]
                i+=1
        
        if mini==float('inf'):
            return 0
        else:
            return mini