713 Subarray Product Less Than K 乘積小于K的子數(shù)組

Description:
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.

Example:

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 * 10^4
1 <= nums[i] <= 1000
0 <= k <= 10^6

題目描述:
給定一個(gè)正整數(shù)數(shù)組 nums。

找出該數(shù)組內(nèi)乘積小于 k 的連續(xù)的子數(shù)組的個(gè)數(shù)。

示例 :

示例 1:

輸入: nums = [10,5,2,6], k = 100
輸出: 8
解釋: 8個(gè)乘積小于100的子數(shù)組分別為: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘積小于100的子數(shù)組。

說(shuō)明:

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

思路:

雙指針?lè)?br> 假設(shè) cur = nums[left] * nums[left + 1] * ... * nums[right - 1] * nums[right]
則如果 cur < k, 說(shuō)明以 nums[left:right + 1] 之間的子數(shù)組都滿足
result += right - left + 1(區(qū)間長(zhǎng)度)
時(shí)間復(fù)雜度為 O(mn), 空間復(fù)雜度為 O(n)

代碼:
C++:

class Solution 
{
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) 
    {
        int result = 0, left = 0, n = nums.size(), cur = 1;
        if (!k or k == 1) return result;
        for (int right = 0; right < n; right++) 
        {
            cur *= nums[right];
            while (cur >= k) cur /= nums[left++];
            result += right - left + 1;
        }
        return result;
    }
};

Java:

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int result = 0, left = 0, n = nums.length, cur = 1;
        if (k == 0 || k == 1) return result;
        for (int right = 0; right < n; right++) {
            cur *= nums[right];
            while (cur >= k) cur /= nums[left++];
            result += right - left + 1;
        }
        return result;
    }
}

Python:

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        result, left, n, cur = 0, 0, len(nums), 1
        if not k or k == 1:
            return result
        for right in range(n):
            cur *= nums[right]
            while cur >= k:
                cur //= nums[left]
                left += 1
            result += right - left + 1
        return result