Hex.*

LC209 - Minimum Size Subarray Sum

Posted on In
Leetcode: 122/2658 (52+57+13)

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 = 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] <= 105

Solution

  • Initialize left=right=0, and call the index closed interval [left, right] a window.
  • Continuously increase the right pointer to expand the window until the string in the window meets the requirements (satisfies >= target).
  • Stop increasing the right, and instead increase the left to shrink the window until the string in the window no longer meets the requirements
  • At the same time, each time left is increased, a round of results must be recorded.
  • Repeat steps until right reaches the end of the string.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# O(n) time | O(n) sapce
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        summ = [0]
        for i in nums:
            summ.append(summ[-1]+i)
        i, j = 0, 1
        ans = len(nums)+1
        while j < len(summ):
            if summ[j] - summ[i] < target:
                j+=1
            else:
                ans = min(ans, j-i)
                i+=1
            
        return 0 if ans == len(nums)+1 else ans

optimize the complexity of space from linear to to constant.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# O(n) time | O(1) space
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left, right = 0, 0
        res = float('inf')
        total = 0
        while right < len(nums):
            total += nums[right]
            while total >= target:
                res = min(res, right-left+1)
                total -= nums[left]
                left+=1
            right +=1
        return 0 if res == float('inf') else res