给定一个正整数数组 nums。
找出该数组内乘积小于 k 的连续的子数组的个数。
示例 1:
输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。
说明:
0 < nums.length <= 50000
0 < nums[i] < 1000
0 <= k < 10^6
//暴力法 很慢
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (nums == null || nums.length < 1 || k <= 1) {
return 0;
}
int count = 0;
for(int i = 0; i < nums.length; i++) {
for(int j = i; j < nums.length; j++) {
if(nums[i] < k && isLessThanK(nums, i, j, k)) {
count++;
} else {
break;
}
}
}
return count;
}
public boolean isLessThanK(int[] nums,int start, int end, int k) {
int tmp = 1;
for(int i = start; i <= end; i++) {
tmp *= nums[i];
if(tmp >= k) {
return false;
}
}
return true;
}
}
双指针+滑动窗口(始终确保滑动窗口的乘积恰好小于k)
可以肯定的是, 乘积小于k的子数组都是以数组元素为末尾的子数组(貌似是废话)
维持两个指针i和left
i代表外层for循环的位置, 换句话说为滑动窗口的右边界
left代表滑动窗口的左边界
我们始终确保滑动窗口里的元素累积结果恰好刚刚小于k, 算上left-1位置的元素肯定会大于等于k
确定这样的滑动窗口之后, 以滑动窗口末位元素结尾的子数组即当前滑动窗口乘积小于k的子数组
假设滑动窗口为[1,2,3], 乘积为7, 那么当前滑动窗口子数组为[3]、[2,3]以及[1,2,3]
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (nums == null || nums.length < 1 || k <= 1) {
return 0;
}
int count = 0;
int multi = 1;
int left = 0;
for(int i = 0; i < nums.length; i++) {
multi *= nums[i];
while(multi >= k) {
multi /= nums[left++];
}
count += i - left + 1;
}
return count;
}
}
