LeetCode 238. 除了自身以外数组的乘积

约 4 分钟
文章信息 18 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 10-20 字节跳动 微软 阿里巴巴 快手 腾讯 百度 京东 拼多多 旷视 虾皮 LeetCode 75 LeetCode 热题 100 面试经典 150 题
标签
数组 前缀和
目录

题目描述

✅ 238. 除自身以外数组的乘积

题意分析

要求返回一个等长数组，第 $i$ 位是原数组中除了 nums[i] 之外所有元素的乘积。注意是「除了自身」而不是「除以自身」，这两件事在有零的时候完全不同。

这道题真正的难点全在附加条件上，必须先把它们摆到台面：不能使用除法，且除返回数组外只允许 $O(1)$ 额外空间（输出数组不计入）。前者堵死了「先求全体乘积再逐个相除」这条最省事的路，后者堵死了「开两个辅助数组分别存左右乘积」这条最直观的路。题目还要求 $O(n)$ 时间，于是三面夹击下，可行解法几乎被唯一确定。

其余约束是友好的：$2 \le n \le 10^5$ 保证数组至少两个元素，不必处理长度为 $1$ 时「除自身外什么都没有」的哲学问题；元素取值在 $[-30, 30]$，且题目明确保证任何前缀或后缀的乘积都落在 $32$ 位整型范围内，所以用 int 累乘不会溢出，不需要换 long。

边界主要看零：数组恰好有一个零时，只有零所在位置的答案非零，其余全为零；有两个及以上零时，答案全为零。好的解法应该自动覆盖这两种情况，而不需要专门数零的个数。负数同理，符号会随乘法自然传递，不用特判。

解法：前缀积 + 后缀积

核心思路

不能使用除法，因此把位置 $i$ 的答案拆成两部分：

\[ans[i] = \left(\prod_{j < i} nums[j]\right) \times \left(\prod_{j > i} nums[j]\right)\]

第一趟从左向右，把 nums[i] 左侧所有元素的乘积写入答案数组；第二趟从右向左，用变量 right 滚动维护右侧乘积，并乘到答案中。复用输出数组保存左侧乘积，就不需要两个额外数组。

两趟都遵守“先用后更新”的不变量：进入第一趟第 $i$ 轮时，left 是 $[0,i)$ 的乘积；进入第二趟第 $i$ 轮时，right 是 $(i,n)$ 的乘积。两者都不含 nums[i]，所以相乘后正好得到答案。空区间的乘积取 $1$，也就无需特判数组两端。

解题步骤

  • 创建答案数组，初始化 left = 1。
  • 从左向右遍历：先令 res[i] = left，再执行 left *= nums[i]。
  • 初始化 right = 1，从右向左遍历：先执行 res[i] *= right，再执行 right *= nums[i]。
  • 返回答案数组。

对 [1,2,3,4]，第一趟得到左侧乘积 [1,1,2,6]；第二趟依次乘上右侧乘积 $1,4,12,24$，得到 [24,12,8,6]。含零数组 [-1,1,0,-3,3] 也会自然得到 [0,0,9,0,0]，无需特判零。

代码实现

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int left = 1;
        for (int i = 0; i < n; i++) {
            res[i] = left;
            left *= nums[i];
        }

        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            res[i] *= right;
            right *= nums[i];
        }
        return res;
    }
}

func productExceptSelf(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    left := 1
    for i := 0; i < n; i++ {
        res[i] = left
        left *= nums[i]
    }

    right := 1
    for i := n - 1; i >= 0; i-- {
        res[i] *= right
        right *= nums[i]
    }
    return res
}

复杂度分析

  • 时间复杂度：$O(n)$，进行两趟线性遍历。
  • 空间复杂度：$O(1)$，不计返回数组时只使用常数变量。

关键点总结

  • 将“除自身外”拆成左侧乘积与右侧乘积，完全避开除法。
  • 两趟都必须先使用当前累计值，再把 nums[i] 乘进去，才能排除自身。
  • 复用答案数组保存左侧乘积，右侧乘积只需一个滚动变量。
  • 零和负数会被乘法自然处理；面试时无需为零另写分支。

易错点总结

  • 用总乘积除以当前值：题目禁止除法，且遇到零会失效。
  • 第一趟先执行 left *= nums[i]：会把自身乘入左侧乘积。
  • 第二趟先更新 right：同样会把自身重复乘入答案。
  • 将 left 或 right 初始化为 $0$：空区间乘积应为乘法单位元 $1$，否则结果会全部归零。
  • 第二趟仍从左向右：无法在访问位置 $i$ 时得到其右侧区间的乘积。

相似题目

题目 难度 考察点
剑指 Offer 66. 构建乘积数组 中等 同题的前后缀积构造
303. 区域和检索 - 数组不可变 简单 前缀和预处理与查询
724. 寻找数组的中心下标 简单 左右两侧和相等
42. 接雨水 困难 前后缀最值
152. 乘积最大子数组 中等 乘法的正负号传递
560. 和为 K 的子数组 中等 前缀和配合哈希计数