209. Minimum Size Subarray Sum

• python3

📎 Problem

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

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

Pseudocode

슬라이딩 윈도우 기법

배열의 특정 구간을 유지하면서 그 구간을 확장하거나 축소하는 방법. 이 문제에서는 윈도우의 합이 target 이상이 될 때까지 오른쪽 끝을 확장하고, 그 이후에 왼쪽 끝을 줄여가면서 최소 길이를 찾는다.

절차

1. 변수 초기화:
   left: 윈도우의 왼쪽 끝을 가리키는 포인터.
   sum: 현재 윈도우 내의 요소들의 합.
   min_length: 조건을 만족하는 부분 배열의 최소 길이를 저장하는 변수. 처음에는 불가능한 값인 float('inf')로 초기화.

2. 오른쪽 끝 확장:
   배열 nums를 순회하면서 각 요소를 sum에 더한다.
   sum이 target 이상이 되면 윈도우의 왼쪽 끝을 줄여가면서 min_length를 업데이트.

3. 왼쪽 끝 축소:
   sum이 target 이상인 동안, 왼쪽 끝(left)을 오른쪽으로 이동시키면서 sum에서 nums[left]를 빼고, 윈도우의 길이를 줄인다.
   그 과정에서 min_length를 업데이트.

4. 결과 반환:
   만약 min_length가 갱신되지 않았다면(여전히 float('inf')라면) 조건을 만족하는 부분 배열이 없다는 의미이므로 0을 반환.
   그렇지 않으면 min_length를 반환.

Code

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

Result

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