209. Minimum Size Subarray Sum

MediumLeetCode

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose 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: 2

Explanation: 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] <= 104

How to solve the problem

• Approach: Sliding Window

Code

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        #slide window
        ans = len(nums) + 1 # Set an absolutely large number to avoid `min`
        s = 0 # sum
        left = 0
        for right,x in enumerate (nums): # x = nums[right]
            s += x
            while s >= target:
                ans = min(ans, right - left + 1)
                s -= nums[left] # Previous `ans` has already remeber the answer, now remove the very left element to check whether the ans can be smaller 
                left += 1
        return ans if ans <= len(nums) else 0

Complexity

• Time complexity: O(n)
• Space complexity: O(1)