[리트코드] 209. Minimum Size Subarray Sum

209. Minimum Size Subarray Sum

문제

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.

 

제한사항

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

 

풀이

투포인터

1. 시작점과 끝점이 0번째 원소를 가리키도록한다.
2. 현재 부분합이 target과 같다면 길이를 계산해 answer 값을 업데이트한다.
3. 현재 부분합이 target보다 작다면 end를 1 증가 시킨다.
4. 현재 부분합이 target보다 크다면 start를 1 증가 시킨다.
5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int: 
        answer = len(nums)
        interval_sum = 0
        end = 0
        
        if sum(nums) < target:
            return 0
        
        for start in range(len(nums)):
            while interval_sum < target and end < len(nums):
                interval_sum += nums[end]
                end += 1
            if interval_sum >= target:
                answer = min(answer, end - start)
            interval_sum -= nums[start]
        return answer

Sliding Window

1. 한번 시행할 때마다 target에서 nums[end] 의 값을 빼준다.
2. 만약 target <= 0 이된다면 이 뜻은 nums[start] + nums[start + 1]+ ..... + nums[end]의 값이 target보다 같거나 크다는 뜻이므로 찾으려는 부분 배열이 된다.
3. 부분 배열의 길이 값을 업데이트 해준다.

예시로 보면 아래와 같다.

target : 7
[2, 3, 1, 2, 4, 3]
​
​
1. 
start = 0 
end = 0
target -= nums[end] (target : 5)
end += 1
​
2.
start = 0 
end = 1
target -= nums[end] (target: 2)
end += 1
​
3. 
start = 0 
end = 2
target -= nums[end]  (target: 1)
end += 1
​
4.
start = 0 
end = 3
target -= nums[end] (target: -1)
​
target <= 0 이므로 [2, 3, 1, 2]의 합이 target보다 크거나 작다는 뜻이다. 
​
부분 배열의 길이는 end - start + 1 = 3 - 0 + 1 = 4
​
다른 부분 집합을 찾기 위해 start의 위치를 옮기며 부분 집합에서 빼준다. 즉 target이 0보다 클 때까지 nums[start]의 값을 더해준다. 
​
end += 1
target += nums[start] (target : 1)
start += 1
​
5.
start = 1
end = 4
​
target -= nums[end] (target: -3)
end += 1
target += nums[start] (target : 0)
start += 1
[1,2,4] 라는 부분 집합을 찾았으므로 start의 위치를 옮기며 부분 집합에서 빼준다.
​
target += nums[start] (target : 1)
start += 1
​
.
.
.
​

전체 코드

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int: 
        start = 0
        result = len(nums) + 1
        
        for end in range(len(nums)):
            target -= nums[end]
            
            while target <= 0:
                print(end, start)
                result = min(result, end - start + 1)
                target += nums[start]
                start += 1
        print()
        return result % (len(nums) + 1)

len(nums) + 1로 초기화하고 결과 값을 나머지 계산한 이유는 부분 배열이 없을 경우 0을 리턴해야하기 때문이다.