238. 除了自身以外数组的乘积（中等）

Blind 75 › 238. 除了自身以外数组的乘积（中等） （第 7 章）
文章工具

题目

给定一个整数数组，请返回一个长度相同的数组：第 i 个数等于原数组里除第 i 个数以外所有数字的乘积。

也就是说，answer[i] = nums[0] × … × nums[i−1] × nums[i+1] × … × nums[n−1]，正好把 nums[i] 自己“挖掉”。

自造示例：nums = [2,3,4,5] → [60,40,30,24]

再带一个含 0 的自造示例：nums = [0,1,2] → [2,0,0]

约束：数组长度 2 ~ 105；每个元素 -30 ~ 30；任意前缀积、后缀积以及每个答案都保证在 32 位整数范围内。

两条硬性要求：不能使用除法；时间复杂度 O(n)（进阶：额外空间 O(1)，输出数组不计入额外空间）。

思路

一句话：把 answer[i] 拆成「左边所有数的乘积」×「右边所有数的乘积」，正反各扫一遍。

最直白的做法是照着定义做：对每个位置 i，把除 i 以外的所有数乘一遍。每个位置要 O(n) 次乘法，n 个位置合计 O(n²)。当 n 到 105 时，约 1010 次运算，一定会超时。

慢在哪里？answer[i] 与 answer[i+1] 只差一个元素，但它们各自的连乘几乎完全重复，暴力法没有复用这些中间结果。

关键观察：设 left[i] 表示 nums[i] 左边所有元素的乘积，right[i] 表示 nums[i] 右边所有元素的乘积，那么 answer[i] = left[i] × right[i]。

left 可以正着递推：left[i] = left[i−1] × nums[i−1]；right 可以倒着递推：right[i] = right[i+1] × nums[i+1]。于是可以用两个数组把问题降到 O(n) 时间、O(n) 空间。

再进一步：left 只依赖前一个值，right 只依赖后一个值，都不需要把整段数组存下来。先把 left 写进输出数组，再倒着把 right 乘回去，就得到 O(1) 额外空间。

解法

使用输出数组 ans 当草稿，分两遍：

  1. 正扫：用变量 prefix 保存「当前位置左边所有数的乘积」，先写入 ans[i]，再把 nums[i] 乘进 prefix。
  2. 倒扫：用变量 suffix 保存「当前位置右边所有数的乘积」，乘回 ans[i]，再把 nums[i] 乘进 suffix。

以 nums = [2,3,4,5] 为例：

位置 inums[i]正扫后 ans[i]（左积）倒扫时 suffix（右积）最终 ans[i]
0216060
1322040
246530
3524124

注意表格里的 suffix 是「还没乘当前 nums[i]」时的右积，正好等于 right[i]。

下图把上面 2 个步骤串成流程，并逐步演示：

238. 除了自身以外数组的乘积（中等） 解法步骤流程图
图① 解法步骤流程图（共 2 步）。
238. 除了自身以外数组的乘积（中等） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Solution {
public:
 vector<int> productExceptSelf(vector<int>& nums) {
 int n = nums.size();
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。