[JS] Minimum Size Subarray Sum

🔒 문제 (LeetCode 209)

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

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

 

🌊 입출력

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

 

---

 

🔑 해결

🌌 알고리즘

1) sliding window - time complexity O(n)

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let result = Infinity;
    let sum = 0;
    let l = 0;
    let r = 0;
    
    while(r < nums.length) {
       sum += nums[r];
        
       while(sum >= target) {
           let len = r - l + 1;
           result = Math.min(result, len);
           sum -= nums[l];
           l++;
       }
        
       r++;
    }
    
    return result === Infinity ? 0 : result;
};