LeetCode 713. 乘积小于 K 的子数组

约 10 分钟
文章信息 7 个分类 6 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 微软 华为
标签
数组 二分查找 滑动窗口 前缀和 滑动窗口经典题 子数组问题
目录

题目描述

✅ 713. 乘积小于 K 的子数组

image-20250420052921389

题意分析

给一个整数数组 nums 和一个整数 k，要求统计有多少个连续非空子数组，它们所有元素的乘积严格小于 k。注意要的是个数，不是把这些子数组列出来，也不是求最长的那一个。

「连续」这两个字把候选集合钉死成了 $O(n^2)$ 个区间——每个子数组由左右端点唯一确定。如果逐个枚举区间再算乘积，是 $O(n^3)$；预先算好前缀积可以降到 $O(n^2)$，但前缀积很快就会溢出，而且题目给的 n 到 $3 \times 10^4$，$O(n^2)$ 是 $9 \times 10^8$ 级别，明显超时。所以必须找到线性做法。

真正的算法信号藏在数据范围里：1 <= nums[i] <= 1000，所有元素都是正整数，没有 0 也没有负数。这一条决定了整道题的解法。正数意味着乘积具有单调性：往窗口右端加一个元素，乘积只增不减；从窗口左端删一个元素，乘积只减不增。有了这层单调性，「满足条件」这个性质对区间就是向内继承的——一个区间合法，它的所有子区间必然也合法。这正是双指针能成立的前提。一旦允许出现 0 或负数，乘积就会来回震荡，窗口一收缩说不定反而变大，这条路立刻断掉。

另一个必须提前想到的点是 k 的取值可以低到 0。由于每个元素至少是 1，任何子数组的乘积也至少是 1，所以 k <= 1 时不可能有任何合法子数组，答案恒为 0。这不只是「顺手写个特判」，它还牵扯到主循环的正确性：如果不拦住这种情况，收缩循环会把左指针一路推过右指针，导致越界或死循环。

边界还有：n 可以是 1；单个元素本身就可能大于等于 k（比如 nums = [1000]、k = 5），此时它自己不合法但不该影响后续统计；乘积可能很大，nums 全是 1000 时哪怕只有几个元素也会冲破 int，需要留意中间量的类型。

解法：正数乘积滑动窗口

核心思路

先看暴力：固定左端点 i，向右扩展右端点 j，累乘并统计。一旦乘积达到 k 就可以提前 break（因为再往右只会更大），所以最坏是 $O(n^2)$。瓶颈在于每次换一个左端点都要从头重算乘积，而这些区间之间高度重叠——[i, j] 和 [i+1, j] 的乘积只差一个因子。

换成「固定右端点」的视角，事情就变了。对每个右端点 right，设 L(right) 是使得区间 [L, right] 乘积小于 k 的最小左端点。由于元素全正、乘积对区间收缩单调不增，[L(right), right] 的所有子区间 [i, right]（L(right) <= i <= right）全都合法，而 i < L(right) 的全都不合法。于是以 right 结尾的合法子数组个数恰好是 right - L(right) + 1，一个减法就统计完了，不需要逐个枚举。把所有右端点的贡献加起来就是答案，这也保证了不重不漏——每个子数组只在它的右端点处被数一次。

更关键的是 L(right) 具有单调性：right 右移一格，乘积只增不减，所需的左边界只会往右走，绝不会往左退。所以左指针全程只向右移动，不用回退，两个指针合起来最多走 $2n$ 步。

由此得到循环不变量：每次即将统计答案时，product 恰好等于区间 [left, right] 的乘积，且这个乘积严格小于 k；同时 left 是满足该条件的最小左端点，即 left - 1 若存在则 [left - 1, right] 的乘积必然大于等于 k。前半句保证统计的都是合法区间，后半句保证没有漏统计。

收缩循环的终止性也依赖正数：每次除掉的 nums[left] 至少是 1，最坏情况下 left 一路推到 right + 1，此时窗口为空、product 回到 1，而前面已经排除了 k <= 1，所以 1 < k 必然成立，循环一定停得下来。这时 right - left + 1 算出的是 0，语义正确——以 right 结尾的合法子数组一个也没有。

解题步骤

  • 开头判 k <= 1 直接返回 0：元素全部大于等于 1，最小可能乘积就是 1，k 不超过 1 时无解。这个特判还兼任了安全阀：没有它，k = 0 时收缩循环因为 product >= 0 恒成立而不断右移 left，最终越界访问 nums[left]。
  • 初始化 left = 0、product = 1、res = 0：乘积的单位元是 1 不是 0，写成 0 会让 product 永远归零、条件永远不满足。
  • 枚举右端点 right，先执行 product *= nums[right]：先扩张再检查，这是滑动窗口的标准节奏。窗口此刻可能非法，正是下一步要修的。
  • while (product >= k) 时除掉 nums[left] 并右移 left：用 while 而不是 if，因为新加入的元素可能很大，一次收缩不足以让乘积回落，[1, 1, 1000] 配 k = 5 就需要连收三次。条件写 >= k 而不是 > k，因为题目要求严格小于 k，等于 k 也不合法。
  • 累加 res += right - left + 1：这一行必须放在收缩之后，此时不变量成立、窗口已合法。它统计的是所有以 right 结尾、左端点落在 [left, right] 内的子数组，长度从 1 到 right - left + 1 各一个。放在收缩之前会把非法窗口也数进去。
  • 遍历结束返回 res：每个右端点贡献一次，累加即为总数。

以 nums = [10, 5, 2, 6]、k = 100 走一遍（期望 8）。k > 1，进入主循环，每轮列出「扩张后的乘积 → 收缩过程 → 窗口 → 本轮贡献 → 累计」。

right = 0：product = 1 * 10 = 10，小于 100 不收缩。窗口 [0, 0] 即 [10]，贡献 0 - 0 + 1 = 1，res = 1。这一个是子数组 [10]。

right = 1：product = 10 * 5 = 50，小于 100 不收缩。窗口 [0, 1]，贡献 1 - 0 + 1 = 2，res = 3。新增的两个是 [5] 和 [10, 5]。

right = 2：product = 50 * 2 = 100，达到 100 不满足严格小于，进入收缩——除掉 nums[0] = 10，product = 10，left = 1；此时 10 < 100，收缩结束。窗口 [1, 2]，贡献 2 - 1 + 1 = 2，res = 5。新增的是 [2] 和 [5, 2]；[10, 5, 2] 乘积正好等于 100 被正确排除，而这一步也顺手说明了为什么条件要写 >= k。

right = 3：product = 10 * 6 = 60，小于 100 不收缩。窗口 [1, 3]，贡献 3 - 1 + 1 = 3，res = 8。新增的是 [6]、[2, 6]、[5, 2, 6]。

遍历结束返回 8，与期望一致。数一下总共 8 个：[10]、[5]、[2]、[6]、[10, 5]、[5, 2]、[2, 6]、[5, 2, 6]，正好不重不漏。

再看一个触发窗口清空的用例，nums = [1, 2, 3]、k = 2。right = 0 时 product = 1 < 2，贡献 1；right = 1 时 product = 2 >= 2，收缩除掉 nums[0] = 1 得 product = 2、left = 1，仍不满足，再除掉 nums[1] = 2 得 product = 1、left = 2，此时 left > right，窗口为空，贡献 1 - 2 + 1 = 0；right = 2 同理收缩到 left = 3，贡献 0。返回 1，只有 [1] 合法，正确。注意这里 left 合法地越过了 right，right - left + 1 算出 0 而不是负数，这是这个式子的一个隐藏优点。

代码实现

class Solution {
    // 当窗口乘积大于等于 k 时，持续移动左指针并除掉左端元素，直到窗口重新满足条件。
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) {
            return 0;
        }

        int left = 0;
        long product = 1;
        int res = 0;

        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];
            while (product >= k) {
                product /= nums[left];
                left++;
            }

            res += right - left + 1;
        }

        return res;
    }
}

func numSubarrayProductLessThanK(nums []int, k int) int {
    // 当窗口乘积大于等于 k 时，持续移动左指针并除掉左端元素，直到窗口重新满足条件。
    if k <= 1 {
        return 0
    }

    left := 0
    product := 1
    res := 0

    for right, val := range nums {
        product *= val
        for product >= k {
            product /= nums[left]
            left++
        }

        res += right - left + 1
    }

    return res
}

复杂度分析

  • 时间复杂度：$O(n)$。凭什么：外层 for 走 n 步，内层 while 看似嵌套，但 left 全程只增不减且不会超过 n，所有轮次的收缩次数加起来最多 n 次，摊还下来每轮是常数。两个指针合计移动至多 $2n$ 步，每步只做一次乘除和比较。
  • 空间复杂度：$O(1)$。凭什么：只用了 left、product、res、right 四个标量，没有前缀积数组、没有哈希表，窗口本身是靠两个下标隐式表示的，不占额外存储。

关键点总结

  • 「统计满足条件的子数组个数」而不是「求最优子数组」时，固定右端点、用 right - left + 1 一次性吃掉一整批是核心技巧，它把逐个枚举压成一次减法，也天然保证了不重不漏（每个子数组只在右端点处被计数）。
  • 双指针能成立的充分条件是性质的单调性：右扩使指标单调变差、左缩使指标单调变好。本题靠「元素全为正」拿到这个单调性，做题时应该先去数据范围里确认这一条，而不是看到子数组就上滑动窗口。
  • 乘法窗口的单位元是 1，收缩时用除法回滚。如果题目允许元素为 0，除法会直接崩，那时要改成对数转加法、或按 0 分段处理，这是本题最常见的变形追问。
  • k <= 1 的特判既是数学结论也是代码的安全阀，它保证了收缩循环一定能终止。能说清「不特判会死循环还是会越界」比只说「要特判」更有说服力。
  • 答案累加的位置（收缩之后而非之前）体现的是循环不变量的作用点，写滑动窗口时应该先明确「在哪一行不变量成立」，再把统计语句放到那里。
  • 面试时值得主动补充的是「为什么 $O(n^2)$ 的前缀积不行」和「负数或 0 会怎样破坏解法」，前者解释为什么要滑窗，后者证明你理解的是前提而不是模板。

易错点总结

  • 漏掉 k <= 1 的特判：nums = [1, 2, 3]、k = 0 时 product >= 0 恒成立，收缩循环把 left 一路推到超出数组长度，访问 nums[left] 抛越界异常。
  • product 初始化成 0：任何数乘 0 还是 0，[10, 5, 2, 6] 配 k = 100 会让 product 永远是 0，每轮都不收缩，把所有 $n(n+1)/2$ 个子数组全数进去，返回 10 而不是 8。
  • 收缩条件写成 product > k：[10, 5, 2]、k = 100 时乘积正好 100 被判为合法，多算出 [10, 5, 2] 这个子数组，答案从 8 变成 9。
  • 收缩用 if 而不是 while：nums = [1, 1, 1000]、k = 5 时读入 1000 后乘积是 1000，只收缩一次得到 1000（除掉的是 1），窗口仍非法就去统计，答案凭空多出两个。
  • 把 res += right - left + 1 写在收缩循环之前：[10, 5, 2]、k = 100 在 right = 2 时用尚未修正的窗口 [0, 2] 统计出 3，包含了乘积等于 100 的非法区间。
  • 贡献写成 res += right - left：漏掉了长度为 1 的子数组 [nums[right]]，[10, 5, 2, 6] 会返回 4 而不是 8，答案系统性偏小 n。
  • 贡献写成 res++，以为每个右端点只贡献一个：只数了以每个位置结尾的最长合法子数组，[10, 5, 2, 6] 返回 4，把「统计个数」做成了「统计位置数」。
  • Java 里 product 用 int：nums 全是 1000 时 4 个元素相乘就是 $10^{12}$，int 溢出成负数，product >= k 判为假，窗口永不收缩，返回一个远超正确值的结果。
  • 收缩时先 left++ 再 product /= nums[left]：除掉的是新左端点而不是要移出窗口的那个元素，[10, 5, 2] 会把 5 除掉却保留 10，product 与窗口彻底脱节，后续统计全错。
  • 误把题目当成求最长子数组：返回的是某个长度而不是计数，[10, 5, 2, 6] 会返回 3，方向性错误且改起来要重写统计逻辑。

相似题目

题目 难度 考察点
209. 长度最小的子数组 中等 求最短长度而非计数，指标是加法和，收缩时机变成「合法后尽量缩」并在缩的过程中取最小
3. 无重复字符的最长子串 中等 窗口指标是字符集合，靠哈希表维护重复情况，求最长而不是个数
904. 水果成篮 中等 约束是「窗口内至多两种元素」，需要计数哈希表判断种类数，收缩条件不是数值比较
1004. 最大连续1的个数 III 中等 窗口指标是 0 的个数上限 k，可以有反转配额，本质是带预算的最长窗口
1658. 将 x 减到 0 的最小操作数 中等 要先把「删两端最少个数」转化成「求中间和为定值的最长窗口」，多一层问题转化
560. 和为 K 的子数组 中等 元素可为负，前缀和不再单调，滑动窗口彻底失效，必须改用前缀和加哈希表计数
930. 和相同的二元子数组 中等 求恰好等于某值的个数，常用「至多 goal 减至多 goal-1」的差分技巧转成两次滑窗
1248. 统计「优美子数组」 中等 把奇数视作 1、偶数视作 0 后与 930 同构，考的是问题映射而不是窗口本身
LCR 008. 长度最小的子数组 中等 与 209 同题，可直接套用求最短长度的模板
LCR 009. 乘积小于 K 的子数组 中等 与本题同题，可直接套用