713. 乘积小于 K 的子数组
题目描述
输入一个正整数数组 nums 和一个整数 k。
统计有多少个连续非空子数组，其所有元素的乘积严格小于 k，返回这个数量。起止位置不同的子数组分别计数。
示例 1
输入：nums = [10,5,2,6], k = 100 输出：8
解释：满足条件的有 [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
解释：正整数的乘积不可能小于 0。
数据范围
1 <= nums.length <= 3 * 10^41 <= nums[i] <= 10000 <= k <= 10^6
解题思路：滑动窗口
所有数都是正整数，窗口扩大时乘积只增不减。用滑动窗口：右端 right 每次右移并乘进 nums[right]；乘积 ≥ k 就不断除掉左端、左端右移。窗口稳定后，以 right 结尾的合法子数组正好是 [left..right]、[left+1..right]……[right..right]，共 right - left + 1 个。
为什么正确
每轮结束时，窗口 [left, right] 是以 right 结尾、乘积 < k 的最长子数组。
复杂度分析
时间 O(n)，每个元素最多进出窗口一次；空间 O(1)。
易错点
k ≤ 1 时没有任何正整数乘积小于 k，必须提前返回 0；否则 while 循环会把 left 推过 right，甚至越界。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if k <= 1:
return 0
prod = 1
ans = left = 0
for right, x in enumerate(nums):
prod *= x
while prod >= k:
prod //= nums[left]
left += 1
ans += right - left + 1
return ansclass Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k <= 1) {
return 0;
}
long prod = 1;
int ans = 0, left = 0;
for (int right = 0; right < nums.length; right++) {
prod *= nums[right];
while (prod >= k) {
prod /= nums[left];
left += 1;
}
ans += right - left + 1;
}
return ans;
}
}class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if (k <= 1) {
return 0;
}
long long prod = 1;
int ans = 0, left = 0;
for (int right = 0; right < (int)nums.size(); right++) {
prod *= nums[right];
while (prod >= k) {
prod /= nums[left];
left += 1;
}
ans += right - left + 1;
}
return ans;
}
};func numSubarrayProductLessThanK(nums []int, k int) int {
if k <= 1 {
return 0
}
prod := 1
ans, left := 0, 0
for right, x := range nums {
prod *= x
for prod >= k {
prod /= nums[left]
left += 1
}
ans += right - left + 1
}
return ans
}var numSubarrayProductLessThanK = function(nums, k) {
if (k <= 1) {
return 0;
}
let prod = 1;
let ans = 0, left = 0;
for (let right = 0; right < nums.length; right++) {
prod *= nums[right];
while (prod >= k) {
prod /= nums[left];
left += 1;
}
ans += right - left + 1;
}
return ans;
};function numSubarrayProductLessThanK(nums: number[], k: number): number {
if (k <= 1) {
return 0;
}
let prod = 1;
let ans = 0, left = 0;
for (let right = 0; right < nums.length; right++) {
prod *= nums[right];
while (prod >= k) {
prod /= nums[left];
left += 1;
}
ans += right - left + 1;
}
return ans;
}其他解法
两种解法都利用“元素为正，左端点右移乘积不增”的单调性；二分查找对每个右端点重新找左端点，滑动窗口让左端点只向右移动，均摊 O(1)。
解法 2：对数前缀和 + 二分查找 时间 O(n log n)，空间 O(n)
取对数把乘积变成和：乘积小于 k 等价于对数和小于 log k。对 log(nums[i]) 求前缀和 logs，它严格单调不减。对每个右端点 j，用二分找到最小的 l，使 logs[j + 1] − logs[l] < log k，以 j 结尾的合法子数组有 j + 1 − l 个。比较时加一个 10⁻¹⁰ 的容差，避免乘积恰好等于 k 时浮点误差导致误判。
取对数后不会溢出，并把问题转成熟悉的前缀和上二分。代价是多一个 log 因子，还要处理浮点误差。
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if k <= 1:
return 0
n = len(nums)
logs = [0.0] * (n + 1)
for i, x in enumerate(nums):
logs[i + 1] = logs[i] + math.log(x)
logk = math.log(k)
ans = 0
for j in range(n):
lo, hi = 0, j + 1
while lo < hi:
mid = (lo + hi) // 2
if logs[j + 1] - logs[mid] < logk - 1e-10:
hi = mid
else:
lo = mid + 1
ans += j + 1 - lo
return ansclass Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k <= 1) return 0;
int n = nums.length;
double[] logs = new double[n + 1];
for (int i = 0; i < n; i++) logs[i + 1] = logs[i] + Math.log(nums[i]);
double logk = Math.log(k);
int ans = 0;
for (int j = 0; j < n; j++) {
int lo = 0, hi = j + 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (logs[j + 1] - logs[mid] < logk - 1e-10) hi = mid;
else lo = mid + 1;
}
ans += j + 1 - lo;
}
return ans;
}
}class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if (k <= 1) return 0;
int n = nums.size();
vector<double> logs(n + 1, 0.0);
for (int i = 0; i < n; i++) logs[i + 1] = logs[i] + log(nums[i]);
double logk = log(k);
int ans = 0;
for (int j = 0; j < n; j++) {
int lo = 0, hi = j + 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (logs[j + 1] - logs[mid] < logk - 1e-10) hi = mid;
else lo = mid + 1;
}
ans += j + 1 - lo;
}
return ans;
}
};func numSubarrayProductLessThanK(nums []int, k int) int {
if k <= 1 {
return 0
}
n := len(nums)
logs := make([]float64, n+1)
for i, x := range nums {
logs[i+1] = logs[i] + math.Log(float64(x))
}
logk := math.Log(float64(k))
ans := 0
for j := 0; j < n; j++ {
lo := sort.Search(j+1, func(m int) bool { return logs[j+1]-logs[m] < logk-1e-10 })
ans += j + 1 - lo
}
return ans
}var numSubarrayProductLessThanK = function(nums, k) {
if (k <= 1) return 0;
const n = nums.length;
const logs = new Float64Array(n + 1);
for (let i = 0; i < n; i++) logs[i + 1] = logs[i] + Math.log(nums[i]);
const logk = Math.log(k);
let ans = 0;
for (let j = 0; j < n; j++) {
let lo = 0, hi = j + 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (logs[j + 1] - logs[mid] < logk - 1e-10) hi = mid;
else lo = mid + 1;
}
ans += j + 1 - lo;
}
return ans;
};function numSubarrayProductLessThanK(nums: number[], k: number): number {
if (k <= 1) return 0;
const n = nums.length;
const logs = new Float64Array(n + 1);
for (let i = 0; i < n; i++) logs[i + 1] = logs[i] + Math.log(nums[i]);
const logk = Math.log(k);
let ans = 0;
for (let j = 0; j < n; j++) {
let lo = 0, hi = j + 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (logs[j + 1] - logs[mid] < logk - 1e-10) hi = mid;
else lo = mid + 1;
}
ans += j + 1 - lo;
}
return ans;
}