[Python] LeetCode 209. Minimum Size Subarray Sum

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

• 자연수를 담고 있는 리스트 nums와 목표 자연수 target이 주어진다
• nums의 subarray 중, subarray 내의 모든 원소의 합이 target 이상이면서 길이가 가장 짧은 subarray의 길이를 구하는 문제

아이디어

1. subarray의 시작 지점이 고정이라면, subarray의 합을 늘리기 위해 끝 지점을 늘려가면서 탐색할 수 있음

2. subarray의 끝 지점을 늘려가다 합이 target 보다 같거나 커지면 더 이상 subarray를 늘려볼 필요가 없음

3. subarray의 합을 줄이기 위해서는 시작 지점을 늘린다

-> 기본적인 two-pointer 흐름이니까 기억해둘 것

 

two-pointer를 이용한 부분합을 구할 때는, 배열의 첫 부분과 마지막 부분만 업데이트

그렇기 때문에 업데이트 되는 원소 값만 더하거나 빼줘야 더 빠르게 부분합을 빠르게 업데이트 할 수 있다

-> sliding window

 

시간복잡도는 O(n)

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        if sum(nums) < target:
            return 0
		# subarray의 처음과 끝 index
        start, end = 0, 0
        answer = len(nums)
        total_sum = nums[0]
        while start <= end:
        	# subarray의 합 검사
            # target 보다 크다면, start를 늘려서 subarray를 줄이기
            if total_sum >= target:
                answer = min(answer, end - start + 1)
                total_sum -= nums[start]
                start += 1
                if start == len(nums):
                    break
            # target 보다 작다면, end를 늘려서 subarray를 늘리기
            else:
                end += 1
                if end == len(nums):
                    break
                total_sum += nums[end]

        return answer