27. Minimum Size Subarray Sum

문제

nums 배열과 target을 인수로 받는다.

요소를 모두 합했을 때 target과 같거나 큰 subarray를 구하라.

subarray는 연속된 요소로 이루어져야 한다.

subarray 중 가장 짧은 subarray의 length를 반환하시오. 

 

내가 생각한 방식

i는 한 칸씩 앞으로 가며 iterate하는 포인터,

j는 subarray를 찾는 포인터.

문제점 : target이 396893380이고 nums 길이가 길 때 Time Limit Exceeded 오류 발생

def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    lengths = []

    for i in range(len(nums)):
        j = i 
        subarray_total = 0
        while subarray_total <= target and j <= len(nums) - 1:
            subarray_total += nums[j]
            j += 1
            if subarray_total >= target: 
                lengths.append(j - i)

    if lengths:
        return min(lengths)
    else:
        return 0

 

해결 방식

https://leetcode.com/problems/minimum-size-subarray-sum/discuss/1006949/Python-Solution

1. target값이거나 target값보다 커질 때까지 iterate하면서 요소를 모두 더함.
2. target값이거나 target값보다 커지면 left 포인터를 앞으로 보내면서 요소를 하나씩 빼봄.
3. 최소 개수로 target 값이 나오는 경우를 찾아서 반환.

def minSubArrayLen(target, nums):
    # 좌측 포인터
    left = 0 
    total = 0

    # 요소 몇 개를 더해서 total이 되는지 알려주는 변수
    # for 문을 돌며 최소값으로 업데이트됨
    result = len(nums) + 1

    for i in range(len(nums)):
        # target에 이를 때 까지 요소를 계속 더함
        total += nums[i]

        # target에 이르렀거나 커졌으면
        while target <= total:
            # 몇 개 요소로 target에 이르렀는지 확인하고 최소값 업데이트
            result = min(result, i - left + 1)
            # left 요소값을 total에서 하나 뺌
            total -= nums[left]
            # left를 한 칸 앞으로 이동
            left += 1

    # result가 업데이트되지 않았다면 0 반환
    return result if result <= len(nums) else 0