LeetCode - 209. Minimum Size Subarray Sum (python)

https://leetcode.com/problems/minimum-size-subarray-sum/?envType=study-plan-v2&envId=top-interview-150

• 난이도: medium
• 알고리즘: sliding window

접근방법

• 입력 크기가 100,000 이므로 O(N) 또는 O(N log N)의 시간복잡도 필요
• nums는 0보다 크므로 nums의 합이 target과 같을 때와 target보다 작을 때를 전처리
• start와 end 인덱스를 설정하고, window의 합이 target보다 작으면 end 인덱스를 증가시키고, target보다 크거나 같으면 min_length를 갱신하고 start 인덱스를 증가시킨다.

소스코드

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        total = sum(nums)
        n = len(nums)
        if total == target:
            return n
        if total < target:
            return 0

        # window: [start_idx:end_idx]
        start_idx = 0; end_idx = 1
        cur_sum = nums[0]
        min_length = n

        while start_idx < n:
            if end_idx == n and cur_sum < target:
                break
            
            if cur_sum < target:
                end_idx += 1
                cur_sum += nums[end_idx - 1]
            else:
                min_length = min(min_length, end_idx - start_idx)
                cur_sum -= nums[start_idx]
                start_idx += 1
        
        return min_length