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

题目描述

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

题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

请不要使用除法，并且在 O(n) 时间复杂度内完成此题。

示例：

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

解题思路

第一步：理解问题约束

这个题的关键约束是：

1. 不能使用除法（否则直接计算总乘积然后除以每个元素即可）
2. 时间复杂度 O(n)
3. 空间复杂度最好是 O(1)，不考虑输出数组的空间

第二步：暴力解法分析（不可行）

最直接的想法是对于每个位置 i，计算除了 i 之外所有元素的乘积：

def productExceptSelf(nums):
    n = len(nums)
    answer = [1] * n
    
    for i in range(n):
        product = 1
        for j in range(n):
            if j != i:
                product *= nums[j]
        answer[i] = product
    
    return answer

时间复杂度：O(n²)，不符合要求。

第三步：前缀与后缀乘积思路

我们可以将问题分解：

• 对于位置 i，结果 = i 左边所有元素的乘积 × i 右边所有元素的乘积

具体来说：

• left[i] = nums[0] × nums[1] × ... × nums[i-1]
• right[i] = nums[i+1] × nums[i+2] × ... × nums[n-1]
• answer[i] = left[i] × right[i]

第四步：空间优化方法

我们可以用输出数组来存储中间结果，避免使用额外空间：

1. 第一遍遍历：计算每个位置左边的乘积，存储在 answer 中
2. 第二遍遍历：从右往左遍历，用变量记录右边乘积，同时更新最终结果

第五步：详细步骤演示

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

步骤1：计算左边乘积

• 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：从右往左，计算右边乘积并更新结果

• 初始化 right_product = 1
• i=3：answer[3] = 6 × 1 = 6，right_product = 1 × 4 = 4
• i=2：answer[2] = 2 × 4 = 8，right_product = 4 × 3 = 12
• i=1：answer[1] = 1 × 12 = 12，right_product = 12 × 2 = 24
• i=0：answer[0] = 1 × 24 = 24，right_product = 24 × 1 = 24

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

第六步：代码实现

def productExceptSelf(nums):
    n = len(nums)
    answer = [1] * n
    
    # 计算左边乘积
    left_product = 1
    for i in range(n):
        answer[i] = left_product
        left_product *= nums[i]
    
    # 计算右边乘积并更新结果
    right_product = 1
    for i in range(n-1, -1, -1):
        answer[i] *= right_product
        right_product *= nums[i]
    
    return answer

第七步：复杂度分析

• 时间复杂度：O(n)，两次遍历数组
• 空间复杂度：O(1)，除了输出数组外只用了常数空间

第八步：验证示例

对于 nums = [1,2,3,4]：

• i=0：左边乘积=1，右边乘积=2×3×4=24，结果=24
• i=1：左边乘积=1，右边乘积=3×4=12，结果=12
• i=2：左边乘积=1×2=2，右边乘积=4，结果=8
• i=3：左边乘积=1×2×3=6，右边乘积=1，结果=6

与题目示例完全一致。

这种方法巧妙地将问题分解为前缀和后缀两部分，通过两次遍历高效解决了问题。