문제 이해

입력

• 정수 배열 nums , 정수 target
• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4

출력

• 최소 길이

요구 사항

• 부분 배열의 합이 target 보다 커야 한다.
• 이때, 부분 배열의 최소 길이
• 시간 복잡도가 O(N^2)은 사용할 수 없다.
• 이진 탐색 혹은 슬라이딩 윈도우 사용해서 최적화

문제 풀이

1. 슬라이딩 윈도우
   • 누적합을 저장할 total
   • 왼쪽 포인터 l
   • 최소 길이를 저장할 min_len
   • 오른쪽 포인터는 for loop의 index를 활용

class Solution(object):
    def minSubArrayLen(self, target, nums):
        # target 보다 같거나 큰 서브 어레이의 최소 길이
        if len(nums) == 0:
            return 0

        l, total, min_len = 0, 0, float('inf')

        for r in range(len(nums)):
		        # loop가 갱신되면 누적합에 nums[r]을 추가해 줌
            total += nums[r]
            
						# total이 traget보다 커질 수 있는 최소 범위 찾기
						# 조건을 만족하면, l += 1해서 범위를 좁혀준다 -> 즉 부분 배열의 길이 축소
            while total >= target:
                min_len = min(min_len, r-l+1)
                total -= nums[l]
                l += 1
                
        return min_len if min_len != float('inf') else 0