[ LeetCode - 209 ] Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/

Minimum Size Subarray Sum - LeetCode

슬라이딩 윈도우(Sliding Window)를 통해서 문제를 접근했다.

비슷한 로직에 대해서 고민하고 있다가 마주한 문제로 정리한 김에 기록으로 남기기로 했다.

 

'target'보다 'greater than or equal' 같거나 큰 수를 구하는 문제로 Array에서 해당 조건을 만족하는 Sub Array중 가장 적은 요소를 갖도록 하여 몇개의 요소가 있는지 구하는 문제

 

[ 📌 풀이 ]

1. Sub Array의 두 개의 포인터 인덱스는 0, 0으로 시작한다.
2. for문은 선형으로 Array를 순회하면서 sums에 값을 더해준다.
3. sums가 'target'보다 크거나 같아질 때(조건에 참일 때) 조건에 해당하니 현재 Sub Array의 요소의 개수를 구하고, 시작 포인터의 인덱스를 증가시킨다.
4. 마지막 return시 ans의 값이 변경되지 않았다면 문제의 요구사항에 맞게 0 반환

[ 문제 풀이 시각화 ]

 

[ 📌 코드 - Python ]

import math

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        srt, sums = 0, 0
        ans = math.inf

        for end, num in enumerate(nums):
            sums += num

            while sums >= target:
                ans = min(ans, end - srt + 1)
                sums -= nums[srt]
                srt += 1
            
        return ans if ans != math.inf else 0