题目描述
给你一个整数数组 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
思路
滑动窗口 （双指针）
- 基本思想：考虑对于每个位置的元素，如果作为一段子数组的结尾，可以形成多少个满足要求的子数组。
- 用滑动窗口寻找最大的满足要求的，然后求以最后位置结尾的所有子数组（其实就是长度），如果超出，则移动左端端点（并删除累成到临时积中的数）
- 维护一个临时积，表示当前滑动窗口的乘积
代码
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int n = nums.length, res = 0;
if (k <= 1) {
return 0;
}
for (int i = 0, j = 0, curSum = 1; i < n; i ++ ) {
curSum *= nums[i];
//若窗口内大于等于规定数，则移动左边窗口
while (curSum >= k) {
curSum /= nums[j ++ ];
}
//统计当前窗口内以nums[i]，结尾的[j, i]内的子数组，其实就是这段长度
res += i - j + 1;
}
return res;
}
}
