713. 乘积小于 K 的子数组

原题链接:713. 乘积小于 K 的子数组

713. 乘积小于 K 的子数组_第1张图片 

solution:

        滑动窗口:维护一个以i为右端点,乘积严格小于K的窗口。
        本体的关键是为什么res每次加i - j + 1
        从窗口定义可以知道,每次更新答案都是更新新的以i为右端点的窗口,而以i为右端点的子数组数目为窗口长度。举个例子:
        当前窗口为:35846,而以6为窗口右端点新增的满足要求的子数组为:

35846,5846,846,46,6,

class Solution {
public:
    int numSubarrayProductLessThanK(vector& nums, int k) {
        if(k <= 1) return 0;
        int res = 0;    //定义返回值
        int n = nums.size();
        for(int i = 0,j = 0,mul = 1;i < n;i++) {
            mul *= nums[i];
            while(mul >= k) mul /= nums[j++];
            res += i - j + 1;   //增加答案
        }
        return res;
    }
};

 

你可能感兴趣的