713.乘积小于K的子数组

题目

https://leetcode-cn.com/problems/subarray-product-less-than-k/

思路

• 当k<=1时，由于数组为正整数数组，明显不存在满足题意的连续子数组，故直接返回结果0。
• 令保存结果的变量res=0，滑动区间左指针left=0，保存滑动区间中元素乘积的变量pro为1。
• 令右指针right从数组左到右滑动，每滑动1次，让pro乘以新元素。如果此时pro大于等于k，则滑动左指针left,每滑动一次令pro除以nums[left]，得到新的滑动区间的元素乘积，直到pro<k。此时，以right为右边界，以滑动区间中任一元素为左边界的子数组都满足题意。由此可以得到以right为子数组右边界的所有子树组的个数right-left+1，将改数值累加至结果res。
• 当right滑动到最右端后，res中便累加了以各个元素为子数组右端点时的有效子数组个数。返回res即可。

代码

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k <= 1){
            return 0;
        }
        int left = 0, right = 0;
        int pro = 1;
        int res = 0;
        while(right < nums.size()){
            pro *= nums[right];
            while(pro >= k){
                pro /= nums[left];
                left++;
            }
            res+= right - left + 1 ;
            right++;
        }
        return res;
    }
};