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

题目 / Problem

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

任意前缀或后缀的乘积都保证可以用 32 位整数表示。

算法必须在 O(n) 时间内运行，并且不能使用除法。

English: Given an integer array nums, return an array answer such that answer[i] equals the product of all elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

The algorithm must run in O(n) time without using division.

示例 / Examples

Example 1

Input:  nums = [1,2,3,4]
Output: [24,12,8,6]

answer[0] = 2 × 3 × 4 = 24
answer[1] = 1 × 3 × 4 = 12
answer[2] = 1 × 2 × 4 = 8
answer[3] = 1 × 2 × 3 = 6

Example 2

Input:  nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

只有下标 2 对应的位置排除了数组中唯一的 0，所以它的结果为 (-1) × 1 × (-3) × 3 = 9。其他位置的乘积都包含 0，结果为 0。
Only index 2 excludes the array's single zero, giving (-1) × 1 × (-3) × 3 = 9. Every other product includes the zero and therefore equals 0.

约束 / Constraints

2 <= nums.length <= 10⁵
-30 <= nums[i] <= 30
输入保证每个 answer[i] 都可以用 32 位整数表示。
Every answer[i] is guaranteed to fit in a 32-bit integer.

进阶 / Follow-up

能否只使用 O(1) 额外空间解决此问题？用于返回答案的输出数组不计入空间复杂度。
Can you solve the problem with O(1) extra space? The output array does not count toward the space-complexity analysis.

关键拆分：左侧乘积 × 右侧乘积 / Key Decomposition: Left Product × Right Product

对于下标 i，除自身以外的所有元素可以分成两部分：
For index i, every element except itself belongs to one of two groups:

answer[i]
= nums[0] × ... × nums[i - 1] × nums[i + 1] × ... × nums[n - 1]
= leftProduct[i] × rightProduct[i]

其中：
Where:

leftProduct[i] 是 i 左侧所有元素的乘积。
leftProduct[i] is the product of all elements to the left of i.
rightProduct[i] 是 i 右侧所有元素的乘积。
rightProduct[i] is the product of all elements to the right of i.

最左侧没有左侧元素，最右侧没有右侧元素。空集合的乘积定义为 1。
The first index has no elements to its left, and the last has none to its right. The product of an empty set is defined as 1.

解题思路：前缀积 + 滚动后缀积 / Approach: Prefix Products + Rolling Suffix Product

为了满足 O(1) 额外空间，可以直接利用输出数组保存左侧乘积：
To achieve O(1) extra space, store left-side products directly in the output array:

第一遍：从左向右 / First Pass: Left to Right

令 answer[i] 保存下标 i 左侧所有元素的乘积：
Let answer[i] store the product of all elements to the left of i:

answer[0] = 1
answer[i] = answer[i - 1] × nums[i - 1]

第二遍：从右向左 / Second Pass: Right to Left

使用变量 suffix 保存当前下标右侧所有元素的乘积：
Use a variable suffix to hold the product of all elements to the right of the current index:

answer[i] = answer[i] × suffix
suffix = suffix × nums[i]

更新 answer[i] 时，suffix 还不包含 nums[i]，因此结果恰好排除了当前元素。之后再将 nums[i] 乘入 suffix，供左侧位置使用。
When updating answer[i], suffix does not yet include nums[i], so the current element is excluded. Then multiply nums[i] into suffix for positions farther left.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function productExceptSelf(nums) {
  const answer = new Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    answer[i] = answer[i - 1] * nums[i - 1];
  }

  let suffix = 1;

  for (let i = nums.length - 1; i >= 0; i--) {
    answer[i] *= suffix;
    suffix *= nums[i];
  }

  return answer;
}

执行过程 / Walkthrough

以 nums = [1,2,3,4] 为例：
For nums = [1,2,3,4]:

第一遍：写入左侧乘积 / First Pass: Store Left Products

`i`	计算 / Calculation	`answer`
初始 / Start	全部初始化为 `1` / Initialize with `1`	`[1,1,1,1]`
1	`answer[1] = answer[0] × nums[0] = 1 × 1`	`[1,1,1,1]`
2	`answer[2] = answer[1] × nums[1] = 1 × 2`	`[1,1,2,1]`
3	`answer[3] = answer[2] × nums[2] = 2 × 3`	`[1,1,2,6]`

此时：
At this point:

answer = [1, 1, 2, 6]
         ↑  ↑  ↑  ↑
左侧积:  1, 1, 1×2, 1×2×3

第二遍：乘入右侧乘积 / Second Pass: Multiply Right Products

`i`	乘入前 `suffix` / Suffix Before	更新 `answer[i]`	更新后 `suffix` / Suffix After	`answer`
3	1	`6 × 1 = 6`	`1 × 4 = 4`	`[1,1,2,6]`
2	4	`2 × 4 = 8`	`4 × 3 = 12`	`[1,1,8,6]`
1	12	`1 × 12 = 12`	`12 × 2 = 24`	`[1,12,8,6]`
0	24	`1 × 24 = 24`	`24 × 1 = 24`	`[24,12,8,6]`

最终返回 [24,12,8,6]。
The final result is [24,12,8,6].

为什么可以正确处理 0？ / Why Does This Handle Zeros?

该算法没有先计算整个数组的总乘积，而是分别计算每个位置左右两侧的乘积。因此 0 会自然影响包含它的前缀或后缀，无需特殊分支。
The algorithm never calculates one total product. It independently combines products from the left and right, so zeros naturally affect the relevant prefixes and suffixes without special cases.

对于 [-1,1,0,-3,3]：
For [-1,1,0,-3,3]:

下标 2 的左侧积是 -1，右侧积是 -9，结果为 9。
At index 2, the left product is -1 and the right product is -9, giving 9.
其他每个位置的左侧或右侧积都包含那个 0，结果自然变为 0。
Every other index has the zero in either its left or right product, naturally producing 0.

复杂度 / Complexity

设数组长度为 n。
Let the array length be n.

时间复杂度：O(n)，数组分别从左到右和从右到左遍历一次。
Time: O(n), because the array is traversed once in each direction.
额外空间复杂度：O(1)，除了返回数组外，只使用变量 suffix。
Extra space: O(1), excluding the returned array; only suffix is used.
输出数组需要 O(n) 空间，但题目明确不将其计入额外空间。
The output array requires O(n) space, but the follow-up explicitly excludes it.

使用两个辅助数组的直观解法 / Intuitive Two-Array Approach

也可以分别创建前缀积数组和后缀积数组：
Two separate arrays can explicitly store prefix and suffix products:

function productExceptSelfWithArrays(nums) {
  const n = nums.length;
  const prefix = new Array(n).fill(1);
  const suffix = new Array(n).fill(1);
  const answer = new Array(n);

  for (let i = 1; i < n; i++) {
    prefix[i] = prefix[i - 1] * nums[i - 1];
  }

  for (let i = n - 2; i >= 0; i--) {
    suffix[i] = suffix[i + 1] * nums[i + 1];
  }

  for (let i = 0; i < n; i++) {
    answer[i] = prefix[i] * suffix[i];
  }

  return answer;
}

时间复杂度 / Time: O(n)
额外空间复杂度 / Extra Space: O(n)，因为额外创建了 prefix 和 suffix。
The separate prefix and suffix arrays require O(n) extra space.

空间优化版本将 prefix 直接写入输出数组，并将 suffix 压缩成一个滚动变量。
The optimized version stores prefix products directly in the output and compresses suffix products into one rolling variable.

为什么不能使用除法？ / Why Is Division Disallowed?

如果没有限制，一个直觉方案是计算总乘积后除以 nums[i]：
Without the restriction, one might compute the total product and divide by nums[i]:

answer[i] = totalProduct / nums[i]

除了题目明确禁止除法外，这种做法遇到 0 时也需要复杂的特殊处理：
Besides being explicitly disallowed, this approach needs complicated zero handling:

一个 0：只有该位置可能得到非零结果。
One zero: only that position may have a nonzero result.
两个或更多 0：所有结果都是 0。
Two or more zeros: every result is 0.

前缀积和后缀积方案无需判断 0 的数量，也不会发生除以零。
The prefix/suffix solution needs no zero-count branches and never divides by zero.

易错点 / Common Pitfalls

不能使用除法。
Do not use division.
answer[0] 和初始 suffix 都应为 1，代表空侧的乘积。
Initialize both answer[0] and suffix to 1, representing an empty-side product.
第二遍必须先执行 answer[i] *= suffix，再执行 suffix *= nums[i]，否则会错误地包含自身。
In the second pass, update answer[i] before multiplying nums[i] into suffix, or the current element will be incorrectly included.
前缀积只包含当前位置左侧的元素，不能包含 nums[i]。
A prefix product must contain only elements to the left, excluding nums[i].
不需要为 0 编写特殊分支，前后缀乘积会自然处理。
No special zero branch is needed; prefix and suffix products handle zeros naturally.
题目要求 O(n) 时间，不能为每个下标重新遍历整个数组。
The required time is O(n); do not rescan the full array for every index.

Product of Array Except Self