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.

예제 풀이

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.

nums 배열에서 합이 7이상인 부분 배열은 [1, 2, 4], [4, 3]이 있다. 그중 가장 짧은 길이를 구해야 하므로 [4, 3]이 답이 된다.

target의 길이가 $10^9$이므로 $O(n^2)$ 풀이는 불가능하다. 따라서 $O(n)$의 풀이인 sliding window 방식 등등을 떠올려봐야 한다.
left, right 포인터는 0부터 시작해서 배열 끝까지 탐색한다.

• left: 예전 값 삭제
• right: 새로운 값 추가
  현재까지의 배열 원소들을 더한 total 변수를 두어 target 값보다 크거나 같은지 확인한다.
• total < target: 계속 더함
• total >= target: 조건을 만족했으므로 길이를 더 줄일 수 있는지 확인할 수 있게 됨
  • answer를 right - left + 1랑 비교하여 갱신
  • left 값을 증가시켜 total 변수에서 제거

수도 코드

n = nums의 길이
left = right = total = 0
answer = n + 1

while right < n:
	total += nums[right]
    
    while target <= total:
    	answer = min(answer, right - left + 1)
        total -= nums[left]
        left += 1

return answer if answer < n + 1 else 0

Solution(Runtime: 1ms)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        final int n = nums.length;
        int answer = n + 1;
        int total = 0;

        for (int left = 0, right = 0; right < n; right++){
            total += nums[right];

            while (target <= total) {
                answer = Math.min(answer, right - left + 1);
                total -= nums[left++];
            }
        }

        if (answer < n + 1) {
            return answer;
        }
        return 0;
    }
}

아래 return의 경우 삼항연산자를 이용하여 return answer < n + 1 ? answer : 0;로 깔끔하게 바꿀 수 있다.
다른 사람들의 풀이에는 최소 길이의 초기값을 INT_MAX로 두었는데 사실 그렇게 까지 큰 값을 사용할 필요는 없다. subarray의 최대 길이는 n이기 때문이다.

누적합과 이진탐색의 풀이도 있었다. 이 방식은 모든 원소에 대해 이진탐색을 진행하므로 $O(nlogn)$의 시간복잡도가 소요된다.