713. Subarray Product Less Than K 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) { // 防止后续 while 越界，注意在此题中 1 是很特殊的数字，可以用 nums = [1, 1, 1], k = 1 验证
            return 0;
        }

        int windowProduct = 1;
        int subArrayCount = 0;

        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            // window: [i, j]
            windowProduct *= nums[j]; // 右端元素进入窗口

            // 保证窗口内的元素乘积小于 k
            while (windowProduct >= k) {
                windowProduct /= nums[i++];
            }
            subArrayCount += j - i + 1; // 以右端元素为右边界的数组的个数
        }

        return subArrayCount;
    }
}

References

713. Subarray Product Less Than K
剑指 Offer II 009. 乘积小于 K 的子数组