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:
1
Input: nums = [10, 5, 2, 6], k = 100
2
​
3
Output: 8
4
​
5
Explanation:
6
The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
7
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
Copied!
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]
1
class Solution {
2
    public int numSubarrayProductLessThanK(int[] nums, int k) {
3
        if (k <= 1) {
4
            return 0;
5
        }
6
​
7
        int prod = 1;
8
        int res = 0;
9
        for (int start = 0, end = 0; end < nums.length; end++) {
10
            prod *= nums[end];
11
​
12
            while (prod >= k) {
13
                prod /= nums[start];
14
                ++start;
15
            }
16
            res += end - start + 1;
17
        }
18
        return res;
19
    }
20
}
Copied!
3. Time & Space Complexity
Two Pointers: 时间复杂度O(n), 空间复杂度O(1)

632 Smallest Range

723 Candy Crush

Last modified 2yr ago

Copy link

Contents

713. Subarray Product Less Than K

1. Question

2. Implementation

3. Time & Space Complexity

713. Subarray Product Less Than K​

1. Question

2. Implementation

3. Time & Space Complexity

713. Subarray Product Less Than K