713 Subarray Product Less Than K

Leetcode

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

Example 1:

Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Example 2:

Input: nums = [1,2,3], k = 0
Output: 0

---

滑动窗口，右指针移动，乘积乘上当前的数，如果超过 k ，左指针不断移动，乘积乘上左指针的数。每次右指针移动时找到的窗口子数组个数为 n(n+1)/2 ，n 为窗口元素个数，正好是 1+2+..+n

public int numSubarrayProductLessThanK(int[] nums, int k) {
    if(nums==null || nums.length==0 || k<=1) return 0;
    int left=0, right=0;
    int product=1;
    int count=0;
    while(right<nums.length){
        product*=nums[right++];
        while(product>=k){
            product/=nums[left++];
        }
        count+=right-left;
    }
    return count;
}