【leetcode每日刷题】【尺取法】713. Subarray Product Less Than K

153 阅读 0 评论 101 点赞

我是靠谱客的博主甜美中心，这篇文章主要介绍【leetcode每日刷题】【尺取法】713. Subarray Product Less Than K，现在分享给大家，希望可以做个参考。

Your are given an array of positive integers nums.

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

Example 1:

复制代码

1
2
3
4
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.

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class num713 {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if(k <= 1) return 0;
int prod = 1, ans = 0, left = 0;
for(int right=0; right< nums.length; right++){
prod *= nums[right];
while(prod >= k) prod /= nums[left++];
ans += right-left+1;
}
return ans;
}
public static void main(String[] args) {
num713 s = new num713();
int[] nums = {10, 5, 2, 6};
int
k = 100;
int result = s.numSubarrayProductLessThanK(nums, k);
System.out.println(result);
}
}