LCR 009-乘积小于 K 的子数组

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

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

注意：本题与主站 713 题相同：<https://leetcode-cn.com/problems/subarray-product-less-
than-k/>

方法一：二分查找

思路与算法

子数组 [i, j] 的元素乘积小于 k，即 \prod_{l=i}^{j} \textit{nums}[l] \lt k。

  • k = 0

    由于元素均为正数，所有子数组乘积均大于 0，因此乘积小于 0 的子数组的数目为 0。

  • k > 0

    我们在计算子数组 [i, j] 的元素乘积 \prod_{l=i}^{j} \textit{nums}[l] 时，会出现整型溢出的情况。为了避免整型溢出，我们将不等式两边取对数得 \log \prod_{l=i}^{j} \textit{nums}[l] = \sum_{l=i}^{j} \log \textit{nums}[l] \lt \log k，因此「子数组 [i, j] 的元素乘积小于 k」等价于「子数组 [i, j] 的元素对数和小于 \log k」。

    我们预处理出数组的元素对数前缀和 logPrefix，即 logPrefix}[i + 1] = \sum_{l=0}^{i} \log \textit{nums}[l]。因为 nums 是正整数数组，所以 logPrefix 是非递减的。

    枚举子数组的右端点 j，在 logPrefix 的区间 [0, j] 内二分查找满足 logPrefix}[j + 1] - \textit{logPrefix}[l] \lt \log k 即 logPrefix}[l] \gt \textit{logPrefix}[j + 1] - \log k 的最小下标 l，那么以 j 为右端点且元素乘积小于 k 的子数组数目为 j + 1 - l。返回所有数目之和。

    double 类型只能保证 15 位有效数字是精确的。为了避免计算带来的误差，我们将不等式 logPrefix}[l] \gt \textit{logPrefix}[j + 1] - \log k 的右边加上 10^{-10（题目中的 double 数值整数部分的数字不超过 5 个），即 logPrefix}[l] \gt \textit{logPrefix}[j + 1] - \log k + 10^{-10，从而防止不等式两边数值相等却被判定为大于的情况。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k == 0:
            return 0
        ans, n = 0, len(nums)
        logPrefix = [0] * (n + 1)
        for i, num in enumerate(nums):
            logPrefix[i + 1] = logPrefix[i] + log(num)
        logK = log(k)
        for j in range(1, n + 1):
            l = bisect_right(logPrefix, logPrefix[j] - logK + 1e-10, 0, j)
            ans += j - l
        return ans
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k == 0) {
            return 0;
        }
        int n = nums.size();
        vector<double> logPrefix(n + 1);
        for (int i = 0; i < n; i++) {
            logPrefix[i + 1] = logPrefix[i] + log(nums[i]);
        }
        double logk = log(k);
        int ret = 0;
        for (int j = 0; j < n; j++) {
            int l = upper_bound(logPrefix.begin(), logPrefix.begin() + j + 1, logPrefix[j + 1] - log(k) + 1e-10) - logPrefix.begin();
            ret += j + 1 - l;
        }
        return ret;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public 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;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int numSubarrayProductLessThanK(int* nums, int numsSize, int k){
    if (k == 0) {
        return 0;
    }
    double *logPrefix = (double *)malloc(sizeof(double) * (numsSize + 1));
    for (int i = 0; i < numsSize; i++) {
        logPrefix[i + 1] = logPrefix[i] + log(nums[i]);
    }
    double logk = log(k);
    int ret = 0;
    for (int j = 0; j < numsSize; 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;
    }
    free(logPrefix);
    return ret;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var numSubarrayProductLessThanK = function(nums, k) {
    if (k === 0) {
        return 0;
    }
    const n = nums.length;
    const logPrefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        logPrefix[i + 1] = logPrefix[i] + Math.log(nums[i]);
    }
    const logk = Math.log(k);
    let ret = 0;
    for (let j = 0; j < n; j++) {
        let l = 0;
        let r = j + 1;
        let idx = j + 1;
        const val = logPrefix[j + 1] - logk + 1e-10;
        while (l <= r) {
            const mid = Math.floor((l + r) / 2);
            if (logPrefix[mid] > val) {
                idx = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        ret += j + 1 - idx;
    }
    return ret;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func numSubarrayProductLessThanK(nums []int, k int) (ans int) {
    if k == 0 {
        return
    }
    n := len(nums)
    logPrefix := make([]float64, n+1)
    for i, num := range nums {
        logPrefix[i+1] = logPrefix[i] + math.Log(float64(num))
    }
    logK := math.Log(float64(k))
    for j := 1; j <= n; j++ {
        l := sort.SearchFloat64s(logPrefix[:j], logPrefix[j]-logK+1e-10)
        ans += j - l
    }
    return
}

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 是数组 nums 的长度。预处理数组 logPrefix 需要 O(n)，枚举加二分查找需要 O(n \log n)。

  • 空间复杂度：O(n)。保存数组 logPrefix 需要 O(n) 的空间。

方法二：滑动窗口

思路与算法

我们固定子数组 [i, j] 的右端点 j 时，显然左端点 i 越大，子数组元素乘积越小。对于子数组 [i, j]，当左端点 i \ge l_1 时，所有子数组的元素乘积都小于 k，当左端点 i \lt l_1 时，所有子数组的元素乘积都大于等于 k。那么对于右端点为 j + 1 的所有子数组，它的左端点 i 就不需要从 0 开始枚举，因为对于所有 i \lt l_1 的子数组，它们的元素乘积都大于等于 k。我们只要从 i = l_1 处开始枚举，直到子数组 i = l_2 时子数组 [l_2, j + 1] 的元素乘积小于 k，那么左端点 i \ge l_2 所有子数组的元素乘积都小于 k。

根据上面的分析，我们枚举子数组的右端点 j，并且左端点从 i = 0 开始，用 prod 记录子数组 [i, j] 的元素乘积。每枚举一个右端点 j，如果当前子数组元素乘积 prod 大于等于 k，那么我们右移左端点 i 直到满足当前子数组元素乘积小于 k 或者 i > j，那么元素乘积小于 k 的子数组数目为 j - i + 1。返回所有数目之和。

prod 的值始终不超过 k \times \max_l {\textit{nums}[l] \，因此无需担心整型溢出的问题。

代码

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        ans, prod, i = 0, 1, 0
        for j, num in enumerate(nums):
            prod *= num
            while i <= j and prod >= k:
                prod //= nums[i]
                i += 1
            ans += j - i + 1
        return ans
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int n = nums.size(), 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;
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public 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;
    }
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
int numSubarrayProductLessThanK(int* nums, int numsSize, int k){
    int ret = 0;
    int prod = 1, i = 0;
    for (int j = 0; j < numsSize; j++) {
        prod *= nums[j];
        while (i <= j && prod >= k) {
            prod /= nums[i];
            i++;
        }
        ret += j - i + 1;
    }
    return ret;
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
var numSubarrayProductLessThanK = function(nums, k) {
    let n = nums.length, ret = 0;
    let prod = 1, i = 0;
    for (let j = 0; j < n; j++) {
        prod *= nums[j];
        while (i <= j && prod >= k) {
            prod /= nums[i];
            i++;
        }
        ret += j - i + 1;
    }
    return ret;
};
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
func numSubarrayProductLessThanK(nums []int, k int) (ans int) {
    prod, i := 1, 0
    for j, num := range nums {
        prod *= num
        for ; i <= j && prod >= k; i++ {
            prod /= nums[i]
        }
        ans += j - i + 1
    }
    return
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。两个端点 i 和 j 的增加次数都不超过 n。

  • 空间复杂度：O(1)。

 Comments
On this page
LCR 009-乘积小于 K 的子数组