238. 除了自身以外数组的乘积

题目链接：238. 除了自身以外数组的乘积

题目描述

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

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

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

核心思考：前缀积与后缀积的交汇

这道题的核心矛盾在于：不能使用除法。如果能用除法，直接计算总乘积再除以当前元素即可（只要处理好 0 的情况）。

在禁止除法的前提下，我们可以观察到：对于下标 i 的元素，其结果实际上是 i 左侧所有元素的乘积 乘以 i 右侧所有元素的乘积。

1. 前缀积阵列 (front)：front[i] 存储 nums[0...i-1] 的乘积。
2. 后缀积阵列 (rear)：rear[i] 存储 nums[i+1...n-1] 的乘积。
3. 最终结果：answer[i] = front[i] * rear[i]。

这种思路将“除自身外的乘积”拆解为两个方向的线性扫描，避开了除法，同时完美符合 $O(n)$ 的时间要求。

解题思路 (Python)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [0] * n
        front = [1] * n
        rear = [1] * n
        
        # 计算每个位置的前缀积
        for x in range(1, n):
            front[x] = front[x - 1] * nums[x - 1]
            
        # 计算每个位置的后缀积
        for x in range(n - 2, -1, -1):
            rear[x] = rear[x + 1] * nums[x + 1]

        # 前后缀积相乘即为结果
        for i in range(n):
            answer[i] = front[i] * rear[i]
            
        return answer

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为数组长度。我们进行了三次独立的线性遍历（两次计算前后缀积，一次合并），总耗时与数组规模成正比。
• 空间复杂度：$O(n)$。本解法使用了 front 和 rear 两个额外的辅助数组来存储中间结果。（注：可以通过直接在结果数组上操作来优化至 $O(1)$ 额外空间，但不计结果数组本身的情况下）。