除自身以外数组的乘积

难度: Medium

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

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

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

示例 1:

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

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

2 <= nums.length <= 10⁵
-30 <= nums[i] <= 30
保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

Submission

运行时间: 26 ms

内存: 21.6 MB

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        answer = [0] * length  # 新学的初始化方法
        
        # 初始化索引左侧的乘积
        answer[0] = 1
        # left
        for i in range(1, length):
            answer[i] = answer[i-1] * nums[i-1]
        
        # 初始化索引右侧的乘积
        R = 1
        for i in reversed(range(length)):
            answer[i] = answer[i] * R
            R *= nums[i]
        
        return answer

Explain

这个题解的思路是用前缀积和后缀积的方式来计算除自身以外数组的乘积。首先用一个数组 answer 存储结果，初始化 answer[0] 为 1，表示索引 0 左侧的乘积为 1。然后从左到右遍历数组，对于索引 i，answer[i] 等于 answer[i-1] 乘以 nums[i-1]，即索引 i 左侧数字的乘积。接着从右到左遍历数组，用变量 R 记录索引 i 右侧数字的乘积，answer[i] 等于其本身乘以 R，然后 R 乘以 nums[i]，继续更新到下一个位置。最终 answer 数组就是所求的结果。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        answer = [0] * length  # 初始化结果数组
        
        # 计算索引左侧的乘积
        answer[0] = 1  # 初始化索引 0 左侧的乘积为 1
        for i in range(1, length):
            answer[i] = answer[i-1] * nums[i-1]  # 索引 i 左侧的乘积等于索引 i-1 左侧的乘积乘以 nums[i-1]
        
        # 计算索引右侧的乘积
        R = 1  # 初始化索引右侧的乘积为 1
        for i in reversed(range(length)):
            answer[i] = answer[i] * R  # 索引 i 的结果等于索引 i 左侧的乘积乘以右侧的乘积
            R *= nums[i]  # 更新右侧乘积
        
        return answer

Explore

初始化`answer[0]`为1是因为需要代表索引0左侧的元素乘积。由于索引0是数组的第一个元素，其左侧没有任何元素，因此左侧元素的乘积应当是乘法的单位元，即1。这样初始化可以确保在后续计算中，索引0位置的输出正确表示除自身外其他元素的乘积。

在计算过程中分两次遍历（从左到右和从右到左）是为了分别计算每个索引位置左侧和右侧的元素乘积。第一次遍历从左到右计算并存储每个位置左边所有元素的乘积。第二次遍历从右到左时，结合已存储的左侧乘积和动态计算的右侧乘积，得到最终的结果。通过这种方式，我们能够在不使用除法的情况下完成计算。理论上，通过一次遍历完成这种计算是不可行的，因为每个位置的计算需要依赖于其左侧和右侧所有元素的乘积，这两个信息在只遍历一次的情况下无法同时得到。

变量`R`在从右到左遍历过程中仅用于累计当前索引右侧的元素乘积。如果`nums`数组中包含0，那么在遍历到0的位置时，`R`将被重置为0（因为乘以0的结果是0）。在继续向左遍历时，`R`将从新的非零值重新开始累计乘积。这种处理方式确保了即使遇到0，计算也能正确反映出，当一个索引位置的元素为0时，除该元素外的乘积应该为0（因为包含了该0元素的乘积）。

如果数组`nums`中包含零，算法在遍历过程中会在遇到0时使得乘积变为0。例如，如果某个位置`i`的元素是0，那么在从左到右的遍历中，所有i之后的位置的左侧乘积都会包含这个0，从而这些位置的乘积都为0。同理，在从右到左遍历时，i位置的右侧乘积也会为0。最终，除了索引i对应的输出为除0之外所有元素的乘积（如果其他位置也没有0，则为所有元素的乘积），其他位置的输出均为0。这确保了输出结果正确反映了除自身以外的乘积。