[JS] Subarray Product Less Than K

🔒 문제 (LeetCode 713)

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

Constraints:

• 1 <= nums.length <= 3 * 104
• 1 <= nums[i] <= 1000
• 0 <= k <= 106

 

🌊 입출력

Example 1:

Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Example 2:

Input: nums = [1,2,3], k = 0
Output: 0

 

---

 

🔑 해결

🌌 알고리즘 - sliding window

left를 고정시켜 right를 움직이며 범위 내의 숫자들의 곱이 k보다 작은지 검사하고, 커지게 되면 작아질 때까지 left를 오른쪽으로 옮긴다.

숫자들의 곱이 k보다 작을때 left ~ right 범위의 수에서 추가되는 새로운 경우의 수는 right - left + 1 개이다.

nums 안의 숫자들이 모두 1 이상이기 때문에 그 곱은 항상 1보다 크다. 따라서 k가 1 이하일 경우 가능한 경우의 수는 0이다.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numSubarrayProductLessThanK = function(nums, k) {
    let count = 0;
    let total = 1;
    let l = 0;
    let r = 0;
    
    if(k <= 1) return 0;
    
    while(r < nums.length) {
        total *= nums[r];
        
        while(total >= k) {
            total /= nums[l];
            l++;
        }
        
        count += r - l + 1;
        r++;
    }
    
    return count;
};