713 Subarray Product Less Than K

713. Subarray Product Less Than K

1. Question

Your are given an array of positive integersnums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less thank.

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.

Note:

0 < nums.length <= 50000.

0 < nums[i] < 1000.

0 <= k < 10^6.

2. Implementation

(1) Two Pointers

思路: 利用滑动窗口的思想，维护满足条件的两个pointer start和end。注意的是每当我们在右边增加一个数时，我们引入了end - start + 1个新的subarray。比如假设我们原来有[1, 2]， 当我们再右边增加3时，我们比原来多了3个subarray，分别是:

[3], [1,3], [2,3]

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) {
            return 0;
        }

        int prod = 1;
        int res = 0;
        for (int start = 0, end = 0; end < nums.length; end++) {
            prod *= nums[end];

            while (prod >= k && start <= end) {
                prod /= nums[start];
                ++start;
            }
            res += end - start + 1;
        }
        return res;
    }
}

3. Time & Space Complexity

Two Pointers: 时间复杂度O(n), 空间复杂度O(1)