题目链接:剑指 Offer II 009. 乘积小于 K 的子数组
方法:同向双指针
解题思路
当 \([l, r]\) 子数组的乘积等于 \(k\) 时,表明以 \(l\) 为左端点且乘积为 \(k\) 的子数组的数量为 \(r - l + 1\),随着数组长度增加乘积一定增大(\([l, r]\) 已经包含端点为 \(1\) 的情况),那么当左端点遍历一遍之后即可以得到结果。
代码
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int l = 0, r = 0, mul = 1, ans = 0;
while (r < nums.size()) {
mul *= nums[r];
while(l <= r && mul >= k) {
mul /= nums[l];
l ++ ;
}
ans += r - l + 1;
r ++ ;
}
return ans;
}
};
复杂度分析
时间复杂度:\(O(n)\);
空间复杂度:\(O(1)\)。