713. Subarray Product Less Than K

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.

滑动窗口,维护一个窗口内的乘积。
当乘积小于目标值时,窗口右侧向右移动。每加入一个新数值,可以增加(j-i+1)个组合。
当乘积大于目标时,窗口左侧向右移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int i = 0;
int j = 0;
int product = nums[0];
int count = 0;

while(i < nums.length && j < nums.length){
if(product < k){
count += (j - i) + 1;
j++;
if(j < nums.length ) product *= nums[j];
}
else{
product /= nums[i];
i++;
}
}
return count;
}
}
Author

Xander

Posted on

2022-04-20

Updated on

2022-04-20

Licensed under

Comments