乘积小于k的连续子数组个数

输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

输入：nums = [1,2,3], k = 0
输出：0

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        # 滑动窗口
        res, left, ji = 0, 0, 1
        for right in range(0, len(nums)):
            ji *= nums[right]
            # 当积超出k的时候ji/nums[left],然后left右移
            while ji >= k and left <= right:
                ji /= nums[left]
                left += 1
            # left->right的情况都符合，并且包含left自己做子数组的时候
            # 每次右指针位移到一个新位置，应该加上 x 种数组组合：
            #  nums[right]
            #  nums[right-1], nums[right]
            #  nums[right-2], nums[right-1], nums[right]
            #  nums[left], ......, nums[right-2], nums[right-1], nums[right]
            # 共有 right - left + 1 种
            res += right - left + 1
        return res

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int n = nums.size();
        if(k==0)
        {
            return 0;
        }

        int l = 0;
        int r = 0;
        int prod = 1;
        int count = 0;
        while(r < n)
        {
            prod *= nums[r];
            while( prod >= k && l <= r)
            {
                prod = prod / nums[l];
                l += 1;
            }
            count += r - l + 1;
            r++;
        }
        return count;
    }
};