[리트코드] 209. Minimum Size Subarray Sum

문제

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

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 <= 10**9
• 1 <= nums.length <= 10**5
• 1 <= nums[i] <= 10**4

 
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)).

---

✔ 문제접근 #1 투포인터[통과] ⭕

Intuition
부분 배열의 양끝을 투포인터로 잡고 부분 배열의 합을 갱신해 나간다.

Algorithm
시작점과 끝점으로하여 부분배열의 합을 계산한다. 시작점과 끝점이 하나씩 추가되고 제거됨에 따라 부분배열의 합도 갱신해준다.

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

    p1, p2 = 0, 0
    n = len(nums)
    min_interval = sys.maxsize
    s = nums[0]
    while p1 <= p2 and p1 < n and p2 < n:
        if s < target:
            p2 += 1
            if 0 <= p2 <n:
                s += nums[p2]

        elif s >= target:
            min_interval = min(min_interval, p2 - p1 + 1)
            s -= nums[p1]
            p1 += 1


    # 
    if min_interval == sys.maxsize:
        return 0
    else:    
        return min_interval

Complexity Analysis

• 시간 복잡도 : O(N)
  • 포인터 1이 배열을 순차탐색 O(N)
  • 포인터 2가 배열을 순차탐색 O(N)
  • 그러므로 전체시작복잡도 : O(N+ N) = O(N)

• 공간복잡도 : O(1)

 

---

기타풀이 및 회고

투포인터를 활용할 수 있는 문제였다. 해당 풀이는 모든 배열의 요소가 양수이기 때문에 가능한 풀이이다. 음수라면 포인터가 움직일 때 증가될지 감소될지 불명확하기 때문에 풀이가 어렵다.

 

문제 요구사항에서 추가로 O(NlogN)에 풀 수 있는 방법이 있는지 풀어보라고 했는데, 내가 생각한 방법은 누적합과 이진탐색을 이용한 방법이다. 주어진 배열들을 0부터 각 요소까지의 누적합을 O(N)에 구할 수 있다.

그리고 각각의 배열을 순회하는데 이때 순회하는 값을 시작점이라고 가정한다. 그리고 나머지 시작점부터 끝점사이에서 이진탑색을 이용하여 해당조건을 만족하는 끝점을 찾고 최소길이를 갱신하는 방법이다.

 

간단히 부분배열의 시작점은 순차탐색으로O(N), 끝점은 이진탐색으로 찾는 방식이다O(logN)

    ans = sys.maxsize
    
    # [start, end] 구간에서의 조건에 맞는 값 찾기
    def binary_search(self, start, end, cum_sum, nums, target):
        fixed_start = start
        
        # print(fixed_start, " -> ",end)
        
        while start <= end:
            mid = (start + end) // 2
            k = cum_sum[mid] - cum_sum[fixed_start] + nums[fixed_start]
            
            if k >= target:
                end = mid - 1
                self.ans = min(self.ans, abs(mid- fixed_start) + 1)
            elif k < target:
                start = mid + 1


    
    
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        
        # 누적합구하기
        cum_sum = [0]*len(nums)
        cum_sum[0] = nums[0]
        for i in range(1, len(nums)):
            cum_sum[i] = cum_sum[i - 1] + nums[i]
            
        
        # start = 시작점
        for start in range(len(nums)):
            # 마지막점 찾기
            self.binary_search(start, len(nums) - 1, cum_sum, nums, target)
        
        
        if self.ans == sys.maxsize:
            return 0
        else:
            return self.ans

 

전체 시간복잡도가 O(NlogN)인만큰 런타임 시간도 조금더 오래 걸린것으로 확인된다.