713. Subarray Product Less Than K

[Tcdian]

713. Subarray Product Less Than K

给定一个正整数数组 nums。

找出该数组内乘积小于 k 的连续的子数组的个数。

Example

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.

Note

• 0 < nums.length <= 50000.
• 0 < nums[i] < 1000.
• 0 <= k < 10^6.

[Tcdian]

Solution

• JavaScript Solution

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

• TypeScript Solution

function numSubarrayProductLessThanK(nums: number[], k: number): number {
    if (k <= 1) {
        return 0;
    }
    let left = 0;
    let right = 0;
    let prefix = 1;
    let result = 0;
    while(left < nums.length) {
        while(prefix < k && right < nums.length) {
            prefix *= nums[right++];
        }
        result += right - left;
        if (prefix >= k) {
            result--;
        }
        prefix /= nums[left++];
    }
    return result;
};