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

Raphael Liu Lv10

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