713. 乘积小于 K 的子数组

题目

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

示例 1：

输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

示例 2：

输入：nums = [1,2,3], k = 0
输出：0

提示:

• 1 <= nums.length <= 3 * 10^4
• 1 <= nums[i] <= 1000
• 0 <= k <= 10^6

解答

思路

和 LC209 一样，也是 枚举右端点，收缩左端点，如果乘积 >= k 就把左端点右移，缩小子数组的长度。那么如何计算子数组的 个数 呢？以 [10, 5, 2, 6] 为例，当我们枚举到 nums[2] = 2 时，它的左端点收缩到了 nums[1] = 5。

问题等价于：左右端点下标为 l, r 时，当右端点 r 保持不变时，如何计算 nums[l..r] 这一段内满足要求的子数组个数？

[l, r], [l + 1, r], ..., [r, r]

这是一个 数学集合问题，由于右端点保持不变，因此个数就是 $r-l+1$。

• 时间复杂度为 $O(n)$
• 空间复杂度为 $O(1)$

代码

C++ 代码

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int ans = 0;
        int prod = 1;
        int left = 0;
        int right = 0;

        if (k <= 1) {
            return 0;
        }

        for (; right < nums.size(); right ++) {
            prod *= nums[right];

            while (prod >= k) {
                prod /= nums[left];
                left ++;
            }

            ans += right - left + 1;
        }

        return ans;
    }
};

注意：由于是要乘积严格小于 k，因此当 k <= 1 时，返回值恒为 0。

Python 代码

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0
        
        ans = 0
        prod = 1
        left = 0

        for right, x in enumerate(nums):
            prod *= x

            while prod >= k:
                prod /= nums[left]
                left += 1
            
            ans += right - left + 1
        
        return ans