238. 除自身以外数组的乘积（Product of Array Except Self）

频次 ★★★★ · 难度 🟡 · 高频：字节/阿里

题目

给定一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。不使用除法，时间复杂度 O(n)。

示例：

输入: nums = [1, 2, 3, 4]
输出: [24, 12, 8, 6]

思路

左右乘积法：

• 每个位置的结果 = 左边所有数的乘积 × 右边所有数的乘积
• 第一遍从左到右累积左侧乘积
• 第二遍从右到左累积右侧乘积，直接乘到结果数组

这样只用一个输出数组，额外空间 O(1)（不计输出数组）。

代码

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    result[0] = 1;
    // 左侧累积
    for (int i = 1; i < n; i++) {
        result[i] = result[i - 1] * nums[i - 1];
    }
    // 右侧累积
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= right;
        right *= nums[i];
    }
    return result;
}

复杂度

• 时间：O(n) — 两趟遍历
• 空间：O(1) — 不计输出数组

边界条件

• 数组含 0：本解法不用除法，天然正确处理 0（若用”总乘积 / 自身”的思路则需要特判 0，且多个 0 时结果全为 0）。
• 数组长度为 1：result[0] = 1（没有其他元素），左侧循环不执行，右侧循环只处理这一个元素，right 保持 1，结果正确。
• 全为负数：乘积符号由个数决定，代码只是纯乘法运算，不需要额外处理符号。

变式

• 如果允许使用除法且数组不含 0：先求总乘积 total，answer[i] = total / nums[i]，代码更短但需要单独处理”数组中有一个 0”（此时只有该位置的结果是 total，其余全为 0）和”有多个 0”（结果全为 0）两种情况，反而比不用除法的解法更容易出 bug。
• 需要输出前缀和而不是前缀积：思路完全一样，把乘法换成加法即可，是同一套”左右扫描累积”模板。

易错点

• 不用除法是题目的强制要求（否则遇到 0 会除零错误），面试中如果第一反应是”总乘积除以自身”，要主动意识到需要特判 0 的情况。
• 第二遍从右向左扫描时，是先用 right 乘到 result[i]，再更新 right *= nums[i]——顺序反了会把当前元素自己也算进右侧乘积里。

面试追问

• 能不能只用一次遍历完成？ 可以：一边从左到右算前缀积存入 result，同时用另一个变量在同一个循环里维护后缀积并从后往前更新（需要用两个下标反向同时跑），本质还是两个方向的信息，只是合并到一次循环里，时间复杂度不变。
• 如果数组特别大，int 类型的乘积会不会溢出？ 会。如果数值范围较大，需要用 long 存储中间结果，这也是面试官常追问的边界细节，题目本身通常会保证结果在 int 范围内，但实际工程中要留意。

关联题

• 同套路：560. 和为 K 的子数组 —— 前缀和思想，本题换成前缀积 × 后缀积
• 易混：152. 乘积最大子数组 —— 连续区间最值是 DP，本题是全体乘积拆两半
• 知识点：前缀思想专题见前缀和与差分