209. Minimum Size Subarray Sum

tags: Leetcode Medium

Source:

Average Rating：

Question Description

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 = 4, nums = [1,4,4]
Output: 1

Example 2

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

Constraints:

• 1 <= target <=
  ${10}^9$
• 1 <= nums.length <=
  ${10}^5$
• 1 <= nums[i] <=
  ${10}^5$

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)).

Question Explanation

English Version For this question, we are expected to find the minimal length of sub-array, which has to be contiguous, and can be larger than the target instead of equal to the target only.

For this question, brute-force is not a wise choice. We should try sliding window which can also be called two-pointers method.

Algorithm:

• We have two pointers, left and right
• Then we change the position of these two pointers until the right pointer reaches the tail of the array
  • left pointer = 0, right = left +1
  • move right to the tail of the array
  • once the sum of array[left,right] >= target
  • left +1
• store the length of each sub-array found
• return the min length of the sub-array

Chinese Version

滑动窗口的核心是明确以下几点：

• 窗口内是什么？
• 如何移动窗口的起始位置？
• 如何移动窗口的结束位置？

首先， 满足形成窗口的条件是，窗口内value的和 >= target. 此时窗口内就是一个符合题目要求的sub-array.

起始位置left移动的条件：当前sum>=target 结束位置移动的条件：right其实就是一个遍历array的指针

整个算法结束的标志：left遍历完整个array

主要逻辑：

如果当前位置下滑动窗口里的值>target，那么缩小一下窗口，再往右划

Code

Python

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        
        minlen = float('inf')
        left = 0
        right = 0
        curSum = 0
        
        while right < len(nums):
            curSum += nums[right]
            
            while curSum >= target:
                minlen = min(minlen, right - left + 1)
                curSum -= nums[left]
                left += 1
            
            right += 1
        
        return 0 if minlen == float('inf') else minlen

Python: same as above

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if sum(nums)==target:
            return len(nums)
        if sum(nums)<target:
            return 0
        left,right,tot=0,0,0
        m=len(nums)
        for right in range(len(nums)):
            tot+=nums[right]
            while tot>=target:
                m=min(m,right-left+1)  #storing minimum length of such subarrays 
                tot-=nums[left]
                left+=1
                
        return m

Linked Questions

904 76

Q&A