[LeetCode | Python] 209. Minimum Size Subarray Sum

느낀점

슬라이딩 윈도우에서는 왼쪽, 오른쪽 인덱스를 잘 구분한 후 오른쪽 인덱스는 선행이니 왼쪽 부분만 조율하면 된다.

문제

https://leetcode.com/problems/minimum-size-subarray-sum/description/?source=submission-noac 

리스트에서 타겟을 넘는 서브배열들을 확인하고, 그 중 가장 짧은 길이를 반환하는 문제이다.

풀이

두 개의 포인터를 기준으로 오른쪽은 그대로 가고, 타겟을 넘어갔는지 안 넘어갔는지만 판단하여 왼쪽 인덱스를 조율한다. 전형적인 슬라이딩 윈도우 문제.

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        min_len = float('inf')
        p1 = 0
        sum_cnt = 0
        for p2 in range(len(nums)):
            sum_cnt += nums[p2]
            while sum_cnt >= target:
                min_len = min(p2-p1+1, min_len)
                sum_cnt -= nums[p1]
                p1 += 1
        return min_len if min_len != float('inf') else 0

 

결과

• 공간복잡도: $$ O(N) $$
• 시간복잡도: $$ O(1) $$