手帐 Blog

主题

复盘 · LC 238 除自身以外数组的乘积 ​

题目 ​

题意 ​

给定整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 以外所有元素的乘积。

  • 题目要求：时间尽量 O(n)，且不要用除法（有 0 时除法也不稳）。
  • 进阶：除答案数组外，空间 O(1)（不计返回数组）。

边界：含一个或多个 0；负数；长度为 2。

涉及算法 ​

标签一句话
前缀积 / 后缀积answer[i] = 左侧全部积 × 右侧全部积
两次扫描先左扫填左积，再右扫乘右积，省掉额外数组

教程对照：思想接近 08 · 前缀和——把「前缀和」换成「前缀积」；不依赖除法。

评价我的解法 ​

今天是「暴力卡超时 → 看提示写出左右积」两连，和 7/30 的 560 同款曲线。

版 1：双重循环（TLE，19/24） ​

我的代码（摘自 index.js）：

javascript
var productExceptSelf = function (nums) {
  const resArr = new Array(nums.length).fill(1);
  for (let i = 0; i < nums.length; i++) {
    const item = nums[i];
    for (let j = 0; j < resArr.length; j++) {
      if (i === j) {
        continue;
      }
      resArr[j] = resArr[j] * item;
    }
  }
  return resArr;
};

对在哪：结果语义正确——每个 item 乘进「除自己以外」的格子。

糙在哪：

  1. O(n²)：n 到 10⁵ 量级必炸；注释也写了超时。
  2. 外层扫贡献、内层更新所有位置，本质就是暴力枚举，没往「左右分解」想。

版 2：左积数组 + 右积滚动（看提示后） ​

我的代码（摘自 index2.js）：

javascript
var productExceptSelf = function (nums) {
  const resArr = new Array(nums.length).fill(1);
  for (let i = 0; i < nums.length; i++) {
    if (i === 0) {
      continue;
    }
    resArr[i] = resArr[i - 1] * nums[i - 1];
  }
  let right = 1;
  for (let i = nums.length - 1; i >= 0; i--) {
    resArr[i] = resArr[i] * right;
    right = right * nums[i];
  }
  return resArr;
};

对在哪：

  1. 左扫：resArr[i] 先存严格左侧积；右扫再用 right 乘右侧积——这就是标准终解骨架。
  2. 额外空间只有标量 right，满足进阶 O(1)（不计返回数组）。
  3. 含 0 时自然正确，不用特判。

可再收：

  1. i === 0 的 continue 可写成 for (let i = 1; ...)，少一层分支。
  2. 注释写「看提示后」——模板要默写稳：口述一句「左积 × 右积，两次扫描」。

小结：首版复杂度没过线；提示后终解档位正确。缺口是独立想到「左右分解」，而不是提示到位才写。

最佳题解 ​

与版 2 同档，写法略收：

javascript
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  const n = nums.length;
  const answer = new Array(n).fill(1);
  for (let i = 1; i < n; i++) {
    answer[i] = answer[i - 1] * nums[i - 1];
  }
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= right;
    right *= nums[i];
  }
  return answer;
};
  • 时间 O(n)，空间 O(1)（不计返回数组）。
  • 为何更优：每个位置只依赖左右两侧积，避免 O(n²) 与除法。

关联题目 ​

题为何相关
42. 接雨水同样「左右扫描信息」合成答案
560. 和为 K 的子数组前缀结构；一个是积，一个是和
152. 乘积最大子数组乘积题，但要处理负号与重置
239. 滑动窗口最大值题号易混；本题是 238 不是 239

一句话带走 ​

除自身乘积：answer[i] = 左积 × 右积，两遍扫描，不用除法。