[Medium] 713. Subarray Product Less Than K

문제

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.

정수 숫자와 정수 k의 배열이 주어지면, 부분 배열의 모든 원소의 곱이 k보다 확실히 작은 연속 부분 배열의 수를 반환한다.

 

예시

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

 

제약 조건

Constraints:

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

 

해결 과정

nums[right]의 값을 product에 곱한다.

product가 k보다 작으면 res에 right - left + 1 값을 더해준다.

right의 인덱스를 증가한다.

이러한 과정을 계속하며 product가 k보다 크거나 같은 경우까지 반복한다.

 

product가 k와 크거나 같으면 nums[left]부터 나누어준다. 

이렇게 k보다 같은 경우를 만들어 res에 값을 넣어준다. 

 

해결 코드

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numSubarrayProductLessThanK = function(nums, k) {    
    if (k <= 1) return 0;
    let res = 0, left = 0, right = 0, product = 1;
    while(right < nums.length) {
        product *= nums[right];
        while(product >= k)  {
            product /= nums[left];
            left++;
        }
        res += right - left + 1;
        right++;
    }
    return res;
};