根据对数运算性质将相乘转为求和问题，用前缀和优化。二分查找，滑动窗口，求解《713. 乘积小于 K 的子数组》
对数运算性质 · 相乘
- 将相乘 → 相加，可以用前缀和
自然对数
以 e 为底的对数
Math.log(x)func Log(a float64) float64例题
713. 乘积小于 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
答案
二分查找
自然对数：相乘 转 求和
var numSubarrayProductLessThanK = function(nums, k) {
const n = nums.length, sums = new Array(n + 1), target = Math.log(k)
sums[0] = 0
let ans = 0
for (let i = 0; i < n; i++) sums[i + 1] = sums[i] + Math.log(nums[i])
for (let j = n; j--;) {
let l = 0, r = j
while (l <= r) {
const m = l + r >>> 1
const sum = sums[j + 1] - sums[m] + 1e-10
if (sum > target) l = m + 1
else r = m - 1
}
ans += j - l + 1
}
return ans
};func numSubarrayProductLessThanK(nums []int, k int) int {
n, ans, target := len(nums), 0, math.Log(float64(k))
sums := make([]float64, n + 1)
for i := 0; i < n; i++ {
sums[i + 1] = sums[i] + math.Log(float64(nums[i]))
}
for j := n - 1; j >= 0; j-- {
l, r := 0, j
for l <= r {
m := (l + r) >> 1
sum := sums[j + 1] - sums[m] + 1e-11
if sum > target {
l = m + 1
} else {
r = m - 1
}
}
ans += j - l + 1
}
return ans
}class Solution {
function numSubarrayProductLessThanK($nums, $k) {
$n = count($nums);
$sums = array_fill(0, $n + 1, 0);
$target = log($k);
$ans = 0;
foreach ($nums as $i => $num) {
$sums[$i + 1] = $sums[$i] + log($nums[$i]);
}
for ($j = $n; $j--;) {
$l = 0;
$r = $j;
while ($l <= $r) {
$m = $l + $r >> 1;
$sum = $sums[$j + 1] - $sums[$m] + 1e-10;
if ($sum > $target) $l = $m + 1;
else $r = $m - 1;
}
$ans += $j - $l + 1;
}
return $ans;
}
}滑动窗口
var numSubarrayProductLessThanK = function(nums, k) {
const n = nums.length
let ans = 0
for (let j = i = 0, prodcut = 1; j < n; j++) {
prodcut *= nums[j]
while (i <= j && prodcut >= k) {
prodcut /= nums[i]
i++
}
ans += j - i + 1
}
return ans
};func numSubarrayProductLessThanK(nums []int, k int) int {
product, ans, i := 1, 0, 0
for j, num := range nums {
product *= num
for i <= j && product >= k {
product /= nums[i]
i++
}
ans += j - i + 1
}
return ans
}class Solution {
function numSubarrayProductLessThanK($nums, $k) {
$n = count($nums);
$product = 1;
$ans = 0;
for ($j = $i = 0; $j < $n; $j++) {
$product *= $nums[$j];
while ($i <= $j && $product >= $k) {
$product /= $nums[$i];
$i++;
}
$ans += $j - $i + 1;
}
return $ans;
}
}
