题目描述
给定一个正整数数组 nums
。
找出该数组内乘积小于 k
的连续的子数组的个数。
样例
输入: 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的子数组。
提示
0 < nums.length <= 50000
.0 < nums[i] < 1000
.0 <= k < 10^6
.
算法
(双指针) $O(n)$
- 双指针问题,对于每个位置 $i$,找到最小的 $j <= i$ 满足闭区间
[j, i]
的乘积小于 $k$,这个位置贡献的答案就是 $i - j + 1$。如果不存在这样的 $j$ 则,不累加答案。 - 显然 $j$ 是随着 $i$ 单调不减,所以我们可以在移动 $i$ 的过程中,不断调整 $j$。
时间复杂度
- 每个位置最多被遍历两次,故时间复杂度为 $O(n)$。
空间复杂度
- 只使用常数个变量,故空间复杂度为 $O(1)$。
C++ 代码
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int n = nums.size(), ans = 0;
int curProduct = 1;
for (int i = 0, j = 0; i < n; i++) {
curProduct *= nums[i];
while (j <= i && curProduct >= k) {
curProduct /= nums[j];
j++;
}
ans += i - j + 1;
}
return ans;
}
};
这个位置贡献的答案就是 i−j+1
怎么理解啊以 $i$ 为右端点所能构成的区间个数