LeetCode 713 乘积小于 K 的子数组
🟡 中等
https://leetcode.cn/problems/subarray-product-less-than-k/description/
注意到数组元素都是大于1的， 因此一旦一个子数组的乘积小于了target， 那么其子数组都是满足的。
每层记录的是: 以right 结尾的所有答案数组个数， 会不会少呢? left 到 right 之间满足条件的不一定要以right 结尾， 那些在这个区间内但是不以right结尾的数组会不会被漏掉了呢? 其实不会， 因为所有数组的右侧结束位置都会被遍历一遍， 和最大子数组和的问题相似， 最大子数组和是枚举开始位置， 这里是枚举的结束位置， 一定不会漏掉.
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if(k<=1) return 0;
//枚举右端点
int ans = 0;
int prod = 1;
int left = 0;
for(int r = 0;r<nums.size();r++){
prod *= nums[r];
while(prod>=k&&r>=left){
prod /=nums[left];
left++;
}
ans+=r-left+1;
}
return ans;
}
};