713. 乘积小于 K 的子数组 Medium

给你一个整数数组 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

解题思路

输入：一个整数数组 nums 和一个整数 k

输出：返回所有元素乘积严格小于 k 的连续子数组的数量

本题属于 可变长度滑动窗口类型 类型。

我们需要用到两个指针来维护一个窗口的大小，再用一个变量 product 记录窗口内的乘积

当 product >= k 时，说明不满足窗口条件需要移动左边界缩短窗口，并更新新的 product

每次移动右边界扩展窗口只要满足条件就更新答案 count += (right - left) + 1

(right - left) + 1 代表着以 right 为结尾的所有合法子数组

代码实现

python

from typing import List

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        # 如果 k 小于等于 1，那么所有乘积都不可能小于 k，直接返回 0
        if k <= 1:
            return 0

        left = 0             # 滑动窗口左边界
        product = 1          # 当前窗口内的乘积
        count = 0            # 满足条件的子数组数量

        # 遍历数组，right 表示滑动窗口的右边界
        for right, num in enumerate(nums):
            product *= num   # 将当前元素加入乘积

            # 如果乘积大于等于 k，移动左边界，直到乘积小于 k
            while product >= k and left <= right:
                product //= nums[left]
                left += 1

            # 当前窗口内的所有子数组都满足乘积小于 k
            count += (right - left + 1)

        return count

javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numSubarrayProductLessThanK = function(nums, k) {
    if (k <= 1) return 0;

    let left = 0;
    let count = 0;
    let product = 1;

    for (let right = 0; right < nums.length; right ++) {
        product *= nums[right];

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

        count += (right - left) + 1;
    }

    return count;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

713 国际版

713 中文版