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:

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

提示:

\(1 \le nums.length \le 3 * 10^4\)
\(1 \le nums[i] \le 1000\)
\(0 \le k \le 10^6\)

算法与思路

双指针 \(O(n)\)

我们可以在数组内设置一个滑动窗口，对于每个 \(right\)，我们需要找到一个最小的 \(left\)，满足

\[\prod_{i=left}^{right} nums[i] < k\]

由于当 \(left\) 增加的时候，这个乘积是单调不增的，因此可以使用双指针算法，单调移动 \(left\)。

我们一重循环枚举每个 \(right\)，同时 \(left\) 单调增加。

在循环的每一步中，先将乘积乘以 \(nums[right]\)。
此时需要向右移动 \(left\)，直到满足乘积小于 \(k\) 的条件。
在每次移动 \(left\) 的操作中，需要将乘积除以 \(nums[left]\)。
当 \(left\) 移动完成后，对于当前的 \(right\)，就包含了 \(right-left+1\) 个乘积小于 \(k\) 的连续子数组。

为什么是 \(right-left+1\)？设 \(length=right-left+1\)。

对于每个 \(right\)，连续数组区间需要包含 \(nums[right]\)，即：

区间长度为 \(1\) 的连续数组个数为 \(1\) 个；
区间长度为 \(2\) 的连续数组个数为 \(1\) 个；
区间长度为 \(3\) 的连续数组个数为 \(1\) 个；
...
区间长度为 \(length-1\) 的连续数组个数为 \(1\) 个；
区间长度为 \(length\) 的连续数组个数为 \(1\) 个。

可以得出，有 \(length\) 个 \(1\)，最终个数为 \(length\)，即 \(right-left+1\)。

时间复杂度：一重枚举所有的right端点，而left只需要移动n次，所以时间复杂度为 \(O(n)\)。

空间复杂度：只会用到常数个变量，所以为 \(O(1)\)。

代码

C++

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) return 0;
        int res = 0, t = 1;
        for (int l = 0, r = 0; r < nums.size(); r++) {
            t *= nums[r];
            while (t >= k) {
                t /= nums[l];
                l++;
            }
            res += r - l + 1;
        }
        return res;
    }
};