[python3] 209. Minimum Size Subarray Sum

풀이 일자: 23.07.06

난이도: [Medium]

분류: [Binary Search, Sliding Window, Prefix Sum]

문제 내용

주어진 array에 대해서 target이 주어졌을 때 해당 target과 같거나 큰 합을 가지는 subarray의 최소 길이를 찾는 문제이다.

 

 

문제 해결 흐름

 

1. 연속적인 subarray의 합이 우선 중요하고 각각의 subarray를 관찰하는 것이 필요하기에 Sliding Window이 적합하다.

→ 이때 가장 중요한 것은 Sliding Window의 핵심 idea인 sum을 구하는 방식이다. 일반적으로 two pointer를 이용하고 sum을 구할 때에는 다시 계산하지 않도록 i가 증가할 때는 sum의 값에 이전의 값을 빼고 j가 증가할 때는 sum의 값에 새로운 값을 더하는 방식으로 이전의 sum을 활용하는 방식을 사용해야 한다,

 

→ 이를 사용하지 않을 경우 큰 데이터셋에 대해서 TLE가 발생한다.

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:

        i, j = 0, 0;
        l = len(nums);
        s = nums[0];

        ans = l;

        if sum(nums) < target:
            return 0;

        while(i!=l and j!=l):
            if s >= target:
                ans = min(ans, j-i+1);
                s -= nums[i];
                i += 1;
            else:
                j += 1;
                if j < l:
                    s += nums[j];
        return ans;

 

Time Complexity:  O(N)

i와 j의 움직임에 따른 복잡도의 편차가 크겠지만 N의 복잡도를 가질 것이다.

 

 

Space Complexity: O(1)

공간복잡도는 현재 변수만을 사용했기 때문에 1의 복잡도를 가질 것으로 보인다.

 

 

다른 해결 방식

1.  Official Solution으로는 나와 같은 방식으로 Sliding Window를 사용하였으며 주된 풀이는 Sliding Window였다. 그 다음으로 prefix sum이나 Binary Search를 이용하였으나 문제에는 크게 적합하지 않은 방식으로 보인다.

 

 

 

문제 링크

Minimum Size Subarray Sum - LeetCode