713-乘积小于K的子数组

LeetCode 713. 乘积小于 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

示例 1：

输入：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 的子数组。

method

滑动窗口[j,i]保持窗口内的元素的乘积小于k，这要满足条件，就可以知道以nums[i]为结尾的满足条件的子数组个数为i-j+1

数组[0,1,2]以2结尾的子数组为[0,1,2],[1,2],[2]，总共3个，即2-0+1

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k <= 1) return 0;
    int n = nums.size();
    int cur = 1;
    int res = 0;
    for (int i = 0, j = 0; i < n; i++) {
        cur *= nums[i];
        while (cur >= k) {
            cur /= nums[j];
            j++;
        }
        res += i - j + 1;   // [j, i]
    }
    return res;
}