713. 乘积小于 K 的子数组
题目描述
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 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 的子数组。
示例 2：
输入：nums = [1,2,3], k = 0
输出：0
方法一：枚举
其实我这个思路也算是滑动窗口，不过我的思路是固定左边界，右边界每次 +1，也是类似于枚举了。
public int numSubarrayProductLessThanK(int[] nums, int k) {
int length = nums.length, ans = 0;
for (int i = 0; i < length; i++) {
int curr = 1;
for (int j = i; j < length; j++) {
curr *= nums[j];
if (curr < k) {
ans++;
} else {
break;
}
}
}
return ans;
}
方法二：滑动窗口
首先定义两个指针 left 和 right，后续遍历数组与记录用，
- 左右指针起始均在位置
0；用右指针遍历数组，每次循环中右指针右移一次； - 移动过程中纪录从左指针到右指针路上的连续数的乘积为
mul； - 如果乘积大于
k了，则左指针右移，注意此处用的是while来使左指针右移，因为实际情况可能是：右指针最后右移一次指向了一个比较大的数使得mul不小于目标值，此时左指针需要右移多次才能使得mul刚小于 k； - 最后用
ans记录mul小于k时的数组组合；
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int n = nums.length, ret = 0;
int prod = 1, i = 0;
for (int j = 0; j < n; j++) {
prod *= nums[j];
while (i <= j && prod >= k) {
prod /= nums[i];
i++;
}
ret += j - i + 1;
}
return ret;
}
}