我来给你讲解 LeetCode 第 238 题「除自身以外数组的乘积」。

题目描述

给你一个整数数组 nums，返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目要求：

• 不能使用除法。
• 在 O(n) 时间复杂度内完成。
• 输出数组不计入空间复杂度分析（即可以认为是 O(1) 额外空间，除了输出数组）。

示例：

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

解题思路

1. 初步思考

如果可以用除法，我们可以先算出所有元素的乘积，然后对于每个 nums[i]，用总乘积除以 nums[i] 即可。
但题目禁止除法，并且如果数组中有 0 也会导致除 0 问题（虽然题目没说无零，但禁用除法意味着我们要用其他方法）。

2. 直接暴力法的缺陷

对于每个位置 i，将其他所有元素乘起来：

• 时间复杂度 O(n²)，太慢，不满足要求。

3. 前缀乘积与后缀乘积的思路

我们注意到：
对于 answer[i]，它等于 nums[0] × nums[1] × ... × nums[i-1]（左边所有数的乘积）
乘以
nums[i+1] × ... × nums[n-1]（右边所有数的乘积）。

因此我们可以预先计算：

• left[i] = 从 nums[0] 乘到 nums[i-1] 的乘积（left[0] = 1）
• right[i] = 从 nums[i+1] 乘到 nums[n-1] 的乘积（right[n-1] = 1）

那么 answer[i] = left[i] * right[i]。

4. 空间优化

上面方法需要两个长度为 n 的数组 left 和 right，空间 O(n)。
但题目希望 O(1) 额外空间（输出数组不算）。

我们可以：

1. 先用输出数组 answer 存储 left 数组（即每个位置左边的乘积）。
2. 然后从右往左遍历，用一个变量 R 记录当前右边的累积乘积，同时更新 answer[i] = answer[i] * R。

这样既避免了额外数组，又满足要求。

详细步骤

例子： nums = [1, 2, 3, 4]

步骤 1：计算左边乘积存入 answer

• answer[0] = 1（因为 0 左边没有元素）
• answer[1] = nums[0] = 1
• answer[2] = nums[0] × nums[1] = 1×2 = 2
• answer[3] = nums[0] × nums[1] × nums[2] = 1×2×3 = 6

此时 answer = [1, 1, 2, 6]（这表示每个位置左边的乘积）

步骤 2：从右往左，乘上右边的乘积
初始化 R = 1（表示最右边元素的右边乘积）

• i = 3：answer[3] = 6 × R = 6 × 1 = 6，然后 R = R × nums[3] = 1 × 4 = 4
• i = 2：answer[2] = 2 × R = 2 × 4 = 8，然后 R = R × nums[2] = 4 × 3 = 12
• i = 1：answer[1] = 1 × R = 1 × 12 = 12，然后 R = R × nums[1] = 12 × 2 = 24
• i = 0：answer[0] = 1 × R = 1 × 24 = 24，然后 R 更新（但之后不用了）

最终 answer = [24, 12, 8, 6]

代码实现（示意）

def productExceptSelf(nums):
    n = len(nums)
    answer = [1] * n
    
    # 左边乘积
    for i in range(1, n):
        answer[i] = answer[i-1] * nums[i-1]
    
    R = 1
    for i in range(n-1, -1, -1):
        answer[i] = answer[i] * R
        R *= nums[i]
    
    return answer

复杂度分析

• 时间复杂度：O(n)，两次遍历。
• 空间复杂度：O(1) 额外空间（输出数组不算）。

这样，我们就完成了不使用除法、O(n) 时间、O(1) 额外空间的解法。