当前位置 博文首页 > weixin_43842888的博客：【左右端点指针】LeetCode - 713. 乘积
题目链接
分析
对于每个 right（i），我们需要找到最小的 left（j），满足 从 left 到 right 的数值乘积小于 k 。由于当 left 增加时，这个乘积是单调不增的，因此我们可以使用双指针的方法，单调地移动 left
算法
我们使用一重循环枚举 right，同时设置 left 的初始值为 0。在循环的每一步中，表示 right 向右移动了一位，将乘积乘以 nums[right]。当乘积大于等于 k 时我们需要向右移动 left，直到满足乘积小于 k 的条件。在每次移动时，需要将乘积除以 nums[left]。当 left 移动完成后，对于当前的 right，就包含了 right?left+1 个乘积小于 k 的连续子数组。
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int len=nums.size(),cnt=0,tmp=1,j=0;
for(int i=0;i<len;i++)
{
tmp *= nums[i];
while(tmp >= k && j <= i)
tmp /= nums[j++];
cnt += i-j+1;
}
return cnt;
}
};
这题一开始我是固定 left 让 right 动的，但发现在 while 判断时 right 指针要么是溢出，要么是会多走或者少走一步，最后终于妥协换成了上面说的解法，就不用担心动的那个指针有溢出情况了
cs