[LeetCode] Minimum Size Subarray Sum

문제

• 문제: https://leetcode.com/problems/minimum-size-subarray-sum/description/
• 난이도: Medium
• 토픽: Array, Binary Search, Sliding Window, Prefix Sum

모든 요소가 양수인 배열 nums와 양수 target이 입력으로 주어지고, nums의 서브 배열들 중 서브 배열의 모든 요소를 더한 값이 target보다 크거나 같은 가장 작은 길이의 서브배열을 구하는 문제이다.

풀이

각 구간사이의 합을 구하는 것이므로 누적합을 사용하면 서브 배열마다 매번 덧셈 연산을 해줄 필요가 없다.

아래의 예제와 같이 누적합을 구해주면 각 구간사이의 합은 쉽게 구할 수 있다.

[2,3,1,2,4,3]    # 입력
[0,2,5,6,8,12,15]    # 누적합

[3, 1, 2]의 합은 8 - 2 = 6이다.

여기서 만약 [3, 1, 2] 서브 배열의 합을 확인하고 싶으면? 아래와 같이 누적합에서 O(1)의 시간으로 구할 수 있다.

구간사이의 합을 구하는걸 아래와 같이 일반화 할 수 있다.

# nums의 left, right
subarray_sum = prefix_sum[right + 1] - prefix_sum[left]

처음에 누적합을 구하는 과정이 O(N)이고, 그 다음부터 구간합을 구하는건 O(1)의 시간이 걸리므로 구간 사이의 합을 빠르게 구해야 하는 경우 유용하게 사용할 수 있다.

이 문제는 누적합을 사용하여 불필요한 연산을 줄여 구간합을 빠르게 구하는것이 핵심이다.

슬라이딩 윈도우 + 구간합

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        answer = float('inf')
        left = 0
        right = 0
        cur = sum(nums[left:right + 1])

        while left <= right and left < len(nums) and right < len(nums):
            if cur < target:
                right += 1
                if right < len(nums):
                    cur += nums[right]
            else:
                answer = min(answer, right - left + 1)
                cur -= nums[left]
                left += 1


        return answer if answer < float('inf') else 0

• 미리 nums[left: right + 1] 사이의 구간합을 미리 계산해둔다.
• cur은 구간 사이의 합이다.
• 만약 구간합이 target보다 작다면 right 포인터를 오른쪽으로 이동하고 cur에 nums[right]를 더해준다.
• 만약 구간합이 target보다 크거나 같으면 left 포인터를 오른쪽으로 이동하고 cur에 nums[left]를 뺀다. 최소 길이를 구하는것이므로 left가 최대한 오른쪽까지 이동하면 최소길이가 된다.

이진 탐색 + 누적합

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        answer = float('inf')

        prefix_sum = [0]
        for i in range(len(nums)):
            prefix_sum.append(prefix_sum[-1] + nums[i])

        for i in range(len(prefix_sum)):
            left = i + 1
            right = len(prefix_sum)

            while left <= right and left < len(prefix_sum):
                mid = (left + right) // 2

                if prefix_sum[mid] - prefix_sum[i] >= target:
                    answer = min(answer, mid - i)
                    right = mid - 1
                else:
                    left = mid + 1

        return answer if answer < float('inf') else 0

• 일반적으로 이진탐색은 정렬이 되어있을때 사용할 수 있다. 이 문제의 nums는 오름차순 정렬이 아니지만, 모든 요소가 양수이므로 누적합은 오름차순 정렬이 될 수 밖에 없다.
• 그럼 prefix_sum의 어느 하나의 인덱스(i)를 골랐을때, prefix_sum[mid] - prefix_sum[i] >= target이 존재하는지만 알면 sum(subarray) >= target인 구간을 쉽게 탐색할 수 있다.
• 다만 찾은 구간이 최소 길이인지는 보장할 수 없으므로 min으로 값을 비교해주며 정답을 구한다.