LeetCode_滑动窗口_二分搜索_中等_713.乘积小于 K 的子数组

悠悠 2023-10-06 23:21 87阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个整数数组 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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/subarray-product-less-than-k

## 2.思路 ##

（1）滑动窗口  
思路参考[本题官方题解][Link 1]。

（2）二分搜索  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————滑动窗口
    class Solution {
        
        public int numSubarrayProductLessThanK(int[] nums, int k) {
        
            int res = 0;
            int length = nums.length;
            int left = 0, right = 0;
            int mul = 1;
            while (right < length) {
        
                mul *= nums[right];
                while (mul >= k && left <= right) {
        
                    mul /= nums[left];
                    //窗口左端点向右移动，即窗口变小
                    left++;
                }
                //记录以 right 为右端点且所有元素的乘积严格小于 k 的连续子数组的数目
                res += right - left + 1;
                right++;
            }
            return res;
        }
    }

//思路2————二分搜索
    class Solution {
        
        public int numSubarrayProductLessThanK(int[] nums, int k) {
        
            if (k == 0) {
        
                return 0;
            }
            // res 记录最终的结果
            int res = 0;
            int length = nums.length;
            double[] logPrefix = new double[length + 1];
            for (int i = 0; i < length; i++) {
        
                logPrefix[i + 1] = logPrefix[i] + Math.log(nums[i]);
            }
            double logK = Math.log(k);
            for (int i = 0; i < length; i++) {
        
                int left = 0;
                int right = i + 1;
                int idx = i + 1;
                double value = logPrefix[i + 1] - logK + 1e-10;
                while (left <= right) {
        
                    int mid = left + (right - left) / 2;
                    if (logPrefix[mid] > value) {
        
                        idx = mid;
                        right = mid - 1;
                    } else {
        
                        left = mid + 1;
                    }
                }
                res += i + 1 - idx;
            }
            return res;
        }
    }

[Link 1]: https://leetcode.cn/problems/subarray-product-less-than-k/solution/cheng-ji-xiao-yu-k-de-zi-shu-zu-by-leetc-92wl/