class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int n=nums.size();
int count = 0;
for(int i=0; i<n; i++) {
int l=i, r=l;
int product = 1;
while(r<n) {
product *= nums[r];
if(product < k) {
count++;
r++;
}
else if(product >= k) {
break;
}
}
}
return count;
}
};
解法二 - Two Pointer + Sliding Window
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if(k <= 1) return 0;
int n=nums.size();
int count = 0, product = 1, l = 0;
for(int r=0; r<n; r++) {
product *= nums[r];
while(product >= k) {
product /= nums[l];
l++;
}
count += r-l+1;
}
return count;
}
};