209. Minimum Size Subarray Sum

209. Minimum Size Subarray Sum

Medium

---

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

 

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

 

문제 접근법

하위 배열의 합이 target보다 크거나 같은경우 하위 배열의 최소 길이를 리턴하는 문제입니다. 

하위 배열의 합을 구하는 문제이기 때문에 슬라이딩 윈도우 기법을 사용하여 풀었습니다.

 

1. window의 시작위치를 나타내는 left와 결과값 ans, 하위 배열의 합을 저장할 sum 변수를 초기화 해준다. 

2. 주어진 nums를 for문으로 순회하면서 값을 sum에 더해준다.

3. sum >= target 인경우 (while)

1. 하위 배열의 길이를 ans에 재할당 해준다.
2. window 사이즈를 초과했기 때문에 sum -= nums[left++] (이때 window 기준은 하위 배열의 합이 target 보다 크거나 같은 경우입니다. )

4. 하위 배열의 합이 조건에 맞지 않은 경우 (ans === Infinity) 0을 리턴해준다. 아닐 경우 ans 리턴 

 

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let left = 0, ans = Infinity, sum = 0;

    for (let right = 0; right < nums.length; right++) {
        sum+= nums[right]
        
        // window 초과
        // 하위 배열의 합이 target 보다 크거나 같을때 하위 배열의 길이를 업데이트 해준다.
        while (sum >= target) { 
            ans = Math.min(ans, right+1-left)
            sum -= nums[left++]
        }
    }

    return ans === Infinity ? 0 : ans;
};