原文链接: https://leetcode-cn.com/problems/subarray-product-less-than-k

英文原文

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

 

Example 1:

Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Example 2:

Input: nums = [1,2,3], k = 0
Output: 0

 

Constraints:

• 1 <= nums.length <= 3 * 104
• 1 <= nums[i] <= 1000
• 0 <= k <= 106

中文题目

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

通过代码

官方题解

方法一：二分查找

分析

我们可以使用二分查找解决这道题目，即对于固定的 $i$，二分查找出最大的 $j$ 满足 $\mathrm{nums}[i]$ 到 $\mathrm{nums}[j]$ 的乘积小于 $k$。但由于乘积可能会非常大（在最坏情况下会达到 $1000^{50000}$），会导致数值溢出，因此我们需要对 $\mathrm{nums}$ 数组取对数，将乘法转换为加法，即 $\log(\prod_i \mathrm{nums}[i]) = \sum_i \log \mathrm{nums}[i]$，这样就不会出现数值溢出的问题了。

算法

对 $\mathrm{nums}$ 中的每个数取对数后，我们存储它的前缀和 $\mathrm{prefix}$，即 $\mathrm{prefix}[i + 1] = \sum_{x=0}^i \mathrm{nums}[x]$，这样在二分查找时，对于 $i$ 和 $j$，我们可以用 $\mathrm{prefix}[j + 1] - \mathrm{prefix}[i]$ 得到 $\mathrm{nums}[i]$ 到 $\mathrm{nums}[j]$ 的乘积的对数。对于固定的 $i$，当找到最大的满足条件的 $j$ 后，它会包含 $j-i+1$ 个乘积小于 $k$ 的连续子数组。

下面的代码和算法中下标的定义略有不同。

[sol1]
class Solution(object):
    def numSubarrayProductLessThanK(self, nums, k):
        if k == 0: return 0
        k = math.log(k)

        prefix = [0]
        for x in nums:
            prefix.append(prefix[-1] + math.log(x))

        ans = 0
        for i, x in enumerate(prefix):
            j = bisect.bisect(prefix, x + k - 1e-9, i+1)
            ans += j - i - 1
        return ans

[sol1]
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k == 0) return 0;
        double logk = Math.log(k);
        double[] prefix = new double[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i+1] = prefix[i] + Math.log(nums[i]);
        }

        int ans = 0;
        for (int i = 0; i < prefix.length; i++) {
            int lo = i + 1, hi = prefix.length;
            while (lo < hi) {
                int mi = lo + (hi - lo) / 2;
                if (prefix[mi] < prefix[i] + logk - 1e-9) lo = mi + 1;
                else hi = mi;
            }
            ans += lo - i - 1;
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(n\log n)$，其中 $n$ 是 $\mathrm{nums}$ 数组的长度。由于二分查找的时间复杂度为 $O(\log n)$，需要进行 $n$ 次，因此总的时间复杂度为 $O(n\log n)$。
• 空间复杂度：$O(n)$，用来存储前缀和数组 $\mathrm{prefix}$。

方法二：双指针

分析

对于每个 $\mathrm{right}$，我们需要找到最小的 $\mathrm{left}$，满足 $\prod_{i=\mathrm{left}}^\mathrm{right} \mathrm{nums}[i] < k$。由于当 $\mathrm{left}$ 增加时，这个乘积是单调不增的，因此我们可以使用双指针的方法，单调地移动 $\mathrm{left}$。

算法

我们使用一重循环枚举 $\mathrm{right}$，同时设置 $\mathrm{left}$ 的初始值为 0。在循环的每一步中，表示 $\mathrm{right}$ 向右移动了一位，将乘积乘以 $\mathrm{nums}[\mathrm{right}]$。此时我们需要向右移动 $\mathrm{left}$，直到满足乘积小于 $k$ 的条件。在每次移动时，需要将乘积除以 $\mathrm{nums}[\mathrm{left}]$。当 $\mathrm{left}$ 移动完成后，对于当前的 $\mathrm{right}$，就包含了 $\mathrm{right} - \mathrm{left} + 1$ 个乘积小于 $k$ 的连续子数组。

[sol2]
class Solution(object):
    def numSubarrayProductLessThanK(self, nums, k):
        if k <= 1: return 0
        prod = 1
        ans = left = 0
        for right, val in enumerate(nums):
            prod *= val
            while prod >= k:
                prod /= nums[left]
                left += 1
            ans += right - left + 1
        return ans

[sol2]
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int prod = 1, ans = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            prod *= nums[right];
            while (prod >= k) prod /= nums[left++];
            ans += right - left + 1;
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是 $\mathrm{nums}$ 数组的长度。循环的时间复杂度为 $O(n)$，而 $\mathrm{left}$ 最多移动 $n$ 次，因此总的时间复杂度为 $O(n)$。
• 空间复杂度：$O(1)$。

统计信息

通过次数	提交次数	AC比率
27636	65380	42.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
乘积最大子数组	中等
和等于 k 的最长子数组长度	中等
和为 K 的子数组	中等
小于 K 的两数之和	简单