LWC 55：713. Subarray Product Less Than K

LWC 55：713. Subarray Product Less Than K

Problem:

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:

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.

```    public int numSubarrayProductLessThanK(int[] nums, int k) {
int cnt = 0;
int n = nums.length;

int p = 1;
int j = 0;
for (int i = 0; i < n; ++i) {
p *= nums[i];
if (p < k) {
cnt += i - j + 1;
}
else { // p >= k
for (; j < n; ){
p /= nums[j++];
if (p < k) break;
}
if (p < k) cnt += i - j + 1;
}
}
return cnt;
}     ```

0 条评论

相关文章

3173

1233

2119

892

1252

892

.NET面试题系列[13] - LINQ to Object

"C# 3.0所有特性的提出都是更好地为LINQ服务的" - Learning Hard

912

1887

3456