[Sliding Window Variable Size] 209. Minimum Size Subarray Sum ★

209. Minimum Size Subarray Sum

 

https://youtu.be/aYqYMIqZx5s?si=65RqKA5cewrGgD2Q

 

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 문제에서 'subarray'가 언급되면 슬라이딩 윈도우 문제일 가능성이 높음

        l, total = 0, 0  # l: 윈도우의 왼쪽 끝 인덱스, total: 현재 윈도우의 합
        res = float("inf")  # 결과 값을 저장할 변수. 최소 길이를 구하기 위해 초기값을 무한대로 설정

        # r은 윈도우의 오른쪽 끝 인덱스를 나타냄
        for r in range(len(nums)):
            total += nums[r]  # 현재 윈도우에 nums[r] 값을 추가하여 합을 업데이트

            # 윈도우 내 합이 target 이상이 될 때까지 반복
            while total >= target:
                # 현재 윈도우 길이(r - l + 1)를 기존 결과 값(res)와 비교하여 최소값을 저장
                res = min(r - l + 1, res)

                # 윈도우의 왼쪽 끝 값을 제외하여 윈도우 축소
                total -= nums[l]
                l += 1  # 윈도우의 왼쪽 끝을 오른쪽으로 이동

        # res 값이 갱신되지 않았다면 가능한 부분 배열이 없다는 뜻이므로 0을 반환
        return 0 if res == float("inf") else res

 

최종 코드

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 연속행렬(subarray)의 합 >= target 만족하는 최소 길이
        # 만족하는게 없으면, 0 리턴

        l = 0  # 윈도우의 왼쪽 경계를 나타냄
        minLen = float('inf')  # 주의! 초기값을 0으로 하면 min() 함수가 올바르게 작동하지 않음
        currSum = 0  # 현재 윈도우의 합

        for r in range(l, len(nums)):  # 윈도우의 오른쪽 경계를 이동하며 순회
            currSum += nums[r]  # 오른쪽 경계에 해당하는 값을 현재 합에 추가

            # if currSum >= target:
            while currSum >= target:  # 현재 합이 target 이상인 경우에만 최소 길이 갱신 시도
                windowsSize = r - l + 1  # 현재 윈도우의 길이 (l == r일 수도 있음)
                minLen = min(minLen, windowsSize)  # 최소 길이 갱신

                # 윈도우의 왼쪽 끝 값을 제외하여 윈도우 축소
                currSum -= nums[l]
                l += 1  # 윈도우의 왼쪽 끝을 오른쪽으로 이동

        # 반복문이 끝난 후에도 minLen이 초기값이라면 조건을 만족한 서브배열이 없었던 것 → 0 반환
        return 0 if minLen == float("inf") else minLen

 

💡 보충 설명 요약:

• float('inf')는 "아직 찾지 못했다"는 의미의 초기값.
• while currSum >= target 안에서 윈도우를 줄이면서도 조건을 만족하는 최소 길이를 찾음.
• 만족하는 서브배열이 없는 경우 대비해 0을 리턴.

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 연속행렬합 >= target 만족하는 최소 길이 return
        minLen = float("inf")
        l=0
        curSum = 0
        for r in range(len(nums)):
            curSum += nums[r]

            while curSum >= target:
                minLen = min(minLen, r-l+1)
                curSum -= nums[l]
                l+=1
        return minLen if minLen != float("inf") else 0