[Leetcode/파이썬] 209. Minimum Size Subarray Sum

Minimum Size Subarray Sum

---

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

 

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

 

Constraints:

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104

 

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

 

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = sm = 0
        res = float('inf')

        for right in range(len(nums)) :
            sm += nums[right]
            
            while sm >= target :
                res = min(res, right - left + 1)
                sm -= nums[left]
                left += 1

        return res if res != float('inf') else 0

투포인터 문제. Follow up 에도 나와있듯이 $O(n)$으로 해결하였다. $O(nlogn)$은 아마 이분탐색도 같이 사용하는 풀이법일 가능성이 높다. 

초기값

• left : 투 포인터 중 하나. right가 주도적으로 움직일 것이고 조건이 맞다면 left도 움직일 것이다.
• sm : 현재 포인터들이 가리키는 값을 더하거나 뺀 총 값을 저장하는 변수
• res : 구하고자 하는 값으로, 최대값으로 설정하여 최소값을 구하고자 한다.

이후 for loop를 돌면서 하나의 값을 뽑아 sm에 더할 것이다. 이때, target 값보다 높아진다면 res를 (right - left + 1)과 비교하여 더 적은 값으로 갱신하고 sm에 가장 앞 쪽의 값, 그러니까 nums[left]에 해당하는 값을 빼준 후 left를 오른쪽으로 한 칸 이동한다.