Subarray Product Less Than K (M)
題目
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.
題意
找到所有的連續子陣列，使其積小于指定值，
思路
遍歷陣列所有元素作為區間右端點；對于每個右端點，找到最左側的元素，使構成的區間的積小于指定值；累加以右端點為終點的子區間的數量，
代碼實作
Java
public int numSubarrayProductLessThanK(int[] nums, int k) {
int count = 0;
int left = 0, product = 1;
for (int right = 0; right < nums.length; right++) {
product *= nums[right];
while (product >= k && left <= right) {
product /= nums[left++];
}
count += right - left + 1;
}
return count;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/135962.html
標籤：其他