[LeetCode/Python] 209. Minimum Size Subarray Sum

📌 Problem

[LeetCode] 209. Minimum Size Subarray Sum

📌 Solution

Idea

• right 포인터를 움직이며 구간 합을 늘리기
• 합이 target 이상이 되면, left를 움직이며 가능한 한 구간을 줄이고 최소 길이 갱신하기
• 전체 배열 끝까지 탐색하기

Code

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        left, total = 0, 0
        ans = n+1

        for right, num in enumerate(nums):
            total += num
            while total >= target:
                ans = min(ans, right - left + 1)
                total -= nums[left]
                left += 1

        return ans if ans != n+1 else 0

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

Cf Sliding Window Simulation

step	right	추가값 x	cur(구간합)	while(cur ≥ 7) 수축 과정	갱신된 ans	최종 (left,cur)
1	0	2	2	—	7	(0,2)
2	1	3	5	—	7	(0,5)
3	2	1	6	—	7	(0,6)
4	3	2	8	길이 4 → ans=4, cur-=2→6	4	(1,6)
5	4	4	10	길이 4 → ans=4, cur-=3→7 → 길이 3 → ans=3, cur-=1→6	3	(3,6)
6	5	3	9	길이 3 → ans=3, cur-=2→7 → 길이 2 → ans=2, cur-=4→3	2	(5,3)