Leetcode 713.乘积小于k的子数组（不定长滑动窗口（求子数组个数））

本文主要是介绍Leetcode 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 <= nums.length <= 3 * 104
• 1 <= nums[i] <= 1000
• 0 <= k <= 106

方法1：滑动窗口 

class Solution {public int numSubarrayProductLessThanK(int[] nums, int k) {if(k <= 1) return 0;int mult = 1, ans = 0, left = 0, right = 0;for(right = 0; right < nums.length; right++){mult *= nums[right];while(mult >= k){mult /= nums[left++];}ans += right - left + 1;//代表当前元素的满足条件的所有可能性}return ans;}
}

 方法2：前缀和 + 二分查找

class Solution {public int numSubarrayProductLessThanK(int[] nums, int k) {if (k == 0) {return 0;}int n = nums.length;double[] logPrefix = new double[n + 1];for (int i = 0; i < n; i++) {logPrefix[i + 1] = logPrefix[i] + Math.log(nums[i]);}double logk = Math.log(k);int ret = 0;for (int j = 0; j < n; j++) {int l = 0;int r = j + 1;int idx = j + 1;double val = logPrefix[j + 1] - logk + 1e-10;while (l <= r) {int mid = (l + r) / 2;if (logPrefix[mid] > val) {idx = mid;r = mid - 1;} else {l = mid + 1;}}ret += j + 1 - idx;}return ret;}
}

这篇关于Leetcode 713.乘积小于k的子数组（不定长滑动窗口（求子数组个数））的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---