LeetCode LCR 009. 乘积小于 K 的子数组

2026-03-28 HGNULB 约 8 分钟

文章信息 5 个分类 3 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 009. 乘积小于 K 的子数组

题意分析

给一个正整数数组 nums 和一个整数 k，统计并返回其中乘积严格小于 k 的连续子数组的数目。

要的是个数而不是具体的子数组，这一点很重要：它意味着我们可以按某种维度把答案批量累加，而不必真的把每个子数组构造出来。数据规模 $n \le 3 \times 10^4$，合法子数组的数量本身就可能达到 $O(n^2) \approx 4.5 \times 10^8$，逐个枚举再判断必然超时，必须找到「一次加一批」的计数方式。

元素全为正整数是核心信号：区间乘积随区间扩张单调不减、随收缩单调不增。有了这条单调性，「以某个右端点结尾的合法子数组」就构成一段连续的左端点区间，可以整段计数；同时也保证了窗口的左端点只会向右移动，永不回退。

需要注意的边界有三个。其一，k 可能小于等于 $1$，而所有元素都是正整数（最小为 $1$），任何非空子数组的乘积至少是 $1$，不可能严格小于 $1$，因此答案必须是 $0$。其二，乘积会迅速膨胀——元素上界 $1000$、长度 $3 \times 10^4$，直接连乘会溢出任何定长整型，所以窗口内的乘积绝不能无限制地累积。其三，判定是「严格小于」而不是「小于等于」，条件写错会整体多算。

解法：滑动窗口维护区间

核心思路

暴力做法是枚举左右端点、逐对算乘积，$O(n^2)$ 甚至 $O(n^3)$。瓶颈有两层：一是重复计算乘积，二是每次只能确认一个子数组是否合法，没法批量统计。

第一个观察是关于批量计数的：固定右端点 j，设满足「乘积小于 k」的最小左端点是 i，那么 [i, j]、[i+1, j]、……、[j, j] 全都合法（因为元素全为正，去掉左边的数只会让乘积更小），一共 j - i + 1 个。反过来，比 i 更靠左的左端点全都不合法。于是每个右端点只需要知道那个临界的 i，就能一次性把 j - i + 1 个子数组计入答案——这一步把 $O(n^2)$ 的枚举压成了 $O(n)$ 次累加。

第二个观察是关于如何维护 i：当 j 右移一格时乘积变大，i 只可能右移或不动，绝不会左移。这正是滑动窗口的前提，于是两个指针都单调向右，总位移 $O(n)$。

要维护的不变量是：s 恒等于窗口 nums[i..j] 的乘积，且每轮内层结束后 s < k 或窗口为空。外层扩张（s *= nums[j]）后立刻内层收缩（s /= nums[i]，i++），把 s 拉回小于 k；此时 i 就是那个临界左端点，直接 answer += j - i + 1。

收缩条件写成 i <= j && s >= k，其中 i <= j 这一半专门用来处理 k <= 1 或某个元素本身就大于等于 k 的情形：窗口被收缩成空之后 s 变回 $1$，若 k <= 1 则 s >= k 仍成立，没有 i <= j 兜底就会让 i 一路越界。窗口为空时 j - i + 1 恰好等于 $0$，答案自然不增，无需特判。

溢出问题也被窗口机制顺带解决了：s 始终被收缩到小于 k（上界 $10^6$ 级），再乘一个不超过 $1000$ 的元素也远在 32 位范围内。Java 里用 long 存 s 是额外的保险，Go 的 int 本身就是 64 位。

解题步骤

初始化 s = 1（乘法的单位元，对应空窗口）、i = 0、answer = 0。初值取 $1$ 而不是 $0$，否则任何乘法都会把 s 钉死在 $0$。

外层 j 从 $0$ 扫到 $n-1$，先执行 s *= nums[j] 扩张窗口。先扩张再收缩，才能保证进入内层时 s 与窗口 [i, j] 严格对应。

内层 while (i <= j && s >= k) 收缩：s /= nums[i++]。用 while 而不是 if，是因为新加入的元素可能很大，需要连续弹出多个左端元素才能把乘积压回 k 以下。i <= j 这个守卫保证窗口收缩到空时能停下，覆盖了 k <= 1 和「单个元素就超标」两类情形。

累加答案 answer += j - i + 1。这一步必须放在内层循环之后：只有收缩完成、s < k 成立时，i 才是真正的临界左端点。窗口为空时 i == j + 1，加的是 $0$，语义正确。

整除是精确的，因为 s 是由这些元素连乘得来的，除回去不会有余数损失——这依赖「窗口内乘积恰好是这些元素之积」这条不变量，一旦某次乘法被跳过，整除就会开始产生偏差。

循环结束直接返回 answer，不需要任何后处理。

以 nums = [10, 5, 2, 6]、k = 100 走一遍，期望答案 8。初始 i = 0, s = 1, answer = 0。j = 0：s = 10，$10 < 100$ 不收缩，answer += 0 - 0 + 1 = 1，累计 $1$（对应 [10]）。j = 1：s = 50，仍小于 $100$，answer += 1 - 0 + 1 = 2，累计 $3$（新增 [5]、[10,5]）。j = 2：s = 100，达到上界不满足严格小于，收缩——s /= 10 得 $10$，i = 1；此时 $10 < 100$ 退出，answer += 2 - 1 + 1 = 2，累计 $5$（新增 [2]、[5,2]；[10,5,2] 因乘积恰为 $100$ 被正确排除）。j = 3：s = 60，小于 $100$，answer += 3 - 1 + 1 = 3，累计 $8$（新增 [6]、[2,6]、[5,2,6]）。返回 8。可以看到 j = 2 那一轮里，s == k 被收缩条件挡住——如果判定写成 s > k，[10,5,2] 就会被错误计入。

代码实现

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        // s 是乘积，初值取乘法单位元 1；用 long 兜住中间的一次乘法。
        long s = 1;
        int answer = 0;
        for (int i = 0, j = 0; j < nums.length; ++j) {
            s *= nums[j];
            // i <= j 这个守卫覆盖 k <= 1 与单个元素超标的情形。
            while (i <= j && s >= k) {
                s /= nums[i++];
            }
            // 收缩完成后 i 才是临界左端点，此时一次性计入 j - i + 1 个子数组。
            answer += j - i + 1;
        }
        return answer;
    }
}

func numSubarrayProductLessThanK(nums []int, k int) int {
    s := 1
    answer, i := 0, 0
    for j, x := range nums {
        s *= x
        for i <= j && s >= k {
            s /= nums[i]
            i++
        }
        answer += j - i + 1
    }
    return answer
}

复杂度分析

时间复杂度：$O(n)$。j 走 $n$ 步，i 单调向右也至多走 $n$ 步，内层 while 的总执行次数被 i 的总位移摊还；每个右端点只做一次常数级的加法就完成了一整批子数组的计数。

空间复杂度：$O(1)$。只用了 s、answer、i、j 四个标量，没有任何随输入规模增长的结构。

关键点总结

「统计满足条件的子数组个数」的通用套路是「固定右端点，数合法左端点的个数」。当合法左端点恰好构成一段连续区间时，就能用 j - i + 1 一次性累加，把枚举压掉一个维度。

元素全为正是乘积/和具备单调性的前提，也是左端点不回退的依据；只要出现 $0$ 或负数，这套推理就要重新设计（含 $0$ 时乘积恒小于正的 k，需要按 $0$ 切段处理）。

收缩条件里的 i <= j 不是可有可无的防御，它是覆盖「k <= 1」「单元素超标」这两类退化输入的唯一手段，同时让空窗口时的 j - i + 1 == 0 自然成立。

乘法窗口比加法窗口多两个坑：初值必须是 $1$、收缩用整除（依赖「乘积恰为窗口元素之积」这条不变量）。写之前先确认这两点，比写完再调试便宜。

面试视角：这题面试官的关注点是「你会不会用 j - i + 1 批量计数」。只要能说清「以 j 结尾的合法子数组的左端点构成一段连续区间」，这题就答对了一半；被追问「如果要求乘积小于等于 k 呢」，答案是把 s >= k 改成 s > k；被追问「如果元素可能是 $0$ 呢」，答案是按 $0$ 把数组切成若干段分别处理，因为 $0$ 会让乘积不再单调。

易错点总结

错误写法：s 初始化为 $0$。乘法把 s 永远钉在 $0$，输入 [10, 5, 2, 6], k = 100 时 s < k 恒成立，返回 $n(n+1)/2 = 10$ 而不是 8。

错误写法：收缩条件写成 s > k。判定从「严格小于」放宽成了「小于等于」，输入 [10, 5, 2, 6], k = 100 会把乘积恰为 $100$ 的 [10, 5, 2] 计入，返回 9。

错误写法：收缩条件漏掉 i <= j。输入 [1, 1, 1], k = 1 时窗口收缩到空后 s 变回 $1$，1 >= 1 仍成立，i 继续右移直到 nums[i] 下标越界。

错误写法：把 answer += j - i + 1 写在内层 while 之前。此时 i 还没收缩到位，输入 [10, 5, 2, 6], k = 100 在 j = 2 处会加上 $3$ 而不是 $2$，返回 9。

错误写法：内层用 if 而不是 while。输入 [1, 2, 3, 100], k = 10 时 j = 3 只弹出一个元素，s 仍然大于等于 k，后续的 j - i + 1 全部偏大，返回值大于正确的 6。

错误写法：Java 里把 s 声明为 int。输入形如 [1000, 1000, 1000, ...], k = 1000000 时，s 在收缩前的那一次乘法可以达到 $10^9$ 量级；虽然本题范围内勉强不溢出，但一旦 k 取到上界就会越过 int 上限并变成负数，s >= k 判定失效。

错误写法：不维护窗口乘积，改为每轮从 i 到 j 重新连乘。逻辑对但复杂度退回 $O(n^2)$，$3 \times 10^4$ 的数据会超时；而且重新连乘的中间值不再被 k 约束，必然溢出。

错误写法：把整除写成浮点除法或先取对数比较。浮点误差会让「乘积恰好等于 k」的临界用例（如 [10, 5, 2], k = 100）随机地被判成小于或大于，结果不稳定。

相似题目

题目	难度	考察点
713. 乘积小于 K 的子数组	中等	与本题同题，可直接套用同一份乘法窗口
209. 长度最小的子数组	中等	求最短长度而非个数，答案要在收缩前更新
LCR 008. 长度最小的子数组	中等	与 209 同题，把乘积换成和，可对照两种更新时机的差别
3. 无重复字符的最长子串	中等	窗口合法性由字符是否重复决定，需额外维护出现集合
1004. 最大连续1的个数 III	中等	收缩依据是窗口内 $0$ 的个数超过 `k`，求的是最长窗口
1658. 将 x 减到 0 的最小操作数	中等	需先把问题反转成「中间最长且和为定值」才能滑窗
992. K 个不同整数的子数组	困难	「恰好 K 个」不能直接滑窗，要用「至多 K 个」减「至多 K-1 个」