LeetCode 剑指 Offer 66. 构建乘积数组

约 4 分钟
文章信息 10 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 剑指 Offer 剑指 Offer（第 2 版） 字节 阿里 虾皮
标签
数组 前缀和

题目描述

✅ 剑指 Offer 66. 构建乘积数组

image-20261001230752596

image-20260928215329598

题意分析

给定数组 a，构造同长度数组，使第 i 项等于输入中除下标 i 之外所有元素的乘积。排除的是当前位置，其他位置即使与它值相同，也仍要参与相乘。

题目禁止使用除法，输入还可能有零或负数。需要直接组合左右两侧的乘积；空数组返回空数组，某一侧没有元素时，其空乘积按一处理。

解法：前后缀乘积

核心思路

[!blue]

对任意位置 i，除自身以外的元素恰好分成两部分：严格位于左侧的元素，以及严格位于右侧的元素。答案就是这两部分乘积的乘积，不需要先计算全数组乘积再相除。

第一遍从左到右，把左侧乘积写入结果数组。最左位置没有左侧元素，所以 res[0] = 1；之后使用 res[i] = res[i - 1] * a[i - 1]，在前一位置的左侧乘积中加入刚跨过的元素，仍然不包含当前位置。

第二遍从右到左，令变量 right 保存当前位置严格右侧的乘积。最右位置右侧为空，初始为一。先执行 res[i] *= right，把两侧信息合起来；再执行 right *= a[i]，让下一轮左移后能把刚经过的当前元素算进右侧。

两遍都只读取输入值，结果数组同时承担左侧预处理与最终输出，因此除了输出之外只需要一个滚动乘积变量。整个过程没有除法，零会自然进入应该包含它的位置；某个位置自身为零时，它自己的答案仍只包含其他位置的值。

解题步骤

  1. 输入为空时返回空数组，否则创建同长度结果并令首项为一。
  2. 从左向右，用前一结果乘前一输入值，填入每个位置严格左侧的乘积。
  3. 初始化右侧乘积 right = 1，从数组末尾向前扫描。
  4. 先把 right 乘入当前结果，再将当前输入值乘入 right，供下一轮使用。
  5. 返回已经合并左右乘积的结果。

代码实现

class Solution {
    // 不能使用除法，因此不能通过总乘积直接相除。
    public int[] constructArr(int[] a) {
        if (a.length == 0) {
            return new int[0];
        }

        int n = a.length;
        int[] res = new int[n];

        res[0] = 1;

        for (int i = 1; i < n; i++) {
            // 结果先只保存当前下标严格左侧的乘积。
            res[i] = res[i - 1] * a[i - 1];
        }

        int right = 1;

        for (int i = n - 1; i >= 0; i--) {
            // 先乘入严格右侧的积，再把当前元素纳入下一轮。
            res[i] = res[i] * right;
            right *= a[i];
        }

        return res;
    }
}

func constructArr(a []int) []int {
    // 不能使用除法，因此不能通过总乘积直接相除。
    if len(a) == 0 {
        return []int{}
    }

    n := len(a)
    res := make([]int, n)
    res[0] = 1

    for i := 1; i < n; i++ {
        // 结果先只保存当前下标严格左侧的乘积。
        res[i] = res[i-1] * a[i-1]
    }

    right := 1
    for i := n - 1; i >= 0; i-- {
        // 先乘入严格右侧的积，再把当前元素纳入下一轮。
        res[i] = res[i] * right
        right *= a[i]
    }

    return res
}

复杂度分析

设数组长度为 $n$。

  • 时间复杂度：$O(n)$，前后各扫描一次。
  • 辅助空间复杂度：$O(1)$，除返回数组外只维护常数个变量；结果数组占 $O(n)$。

关键点总结

[!green]

  • 每个答案拆成严格左侧乘积与严格右侧乘积，始终排除当前元素。
  • 结果数组先存左侧乘积，右侧只需一个变量从右向左维护。
  • 先更新答案、再扩展右侧范围，空乘积用一作为起点。

易错点总结

[!yellow]

  • 前缀转移应乘 a[i - 1]，若乘 a[i] 就提前包含了自身。
  • 第二遍若先更新 right 再写当前答案，也会把自身乘进去。
  • 乘积起点必须为一，设为零会让后续结果全部变零。
  • 不能用总乘积除以当前值，既违反题意，也无法直接处理输入为零的位置。
  • 输入长度为一时，排除自身后没有其他元素，按空乘积定义得到一。

相似题目

题目 难度 关联与区别
724. 寻找数组的中心下标 简单 同样把当前位置两侧拆成前缀与后缀，本题乘积排除自身，原题比较左右和。
42. 接雨水 困难 同样结合左右预处理信息，本题两侧相乘，原题由左右最高边界共同限制水位。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/15472452
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！