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

前缀和, https://leetcode.cn/problems/product-of-array-except-self/

给你一个整数数组 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^5
-30 <= nums[i] <= 30
保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

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

python

from typing import List


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        prefix_mul = []
        ans = [1] * n
        product = 1
        for i in range(n):
            product *= nums[i]
            prefix_mul.append(product)
        suffix_mul = []
        product = 1
        for i in range(n - 1, -1, -1):
            product *= nums[i]
            suffix_mul.append(product)
        suffix_mul.reverse()
        for i in range(n):
            if i == 0:
                ans[i] = suffix_mul[i + 1]
            elif i == n - 1:
                ans[i] = prefix_mul[i - 1]
            else:
                ans[i] = prefix_mul[i - 1] * suffix_mul[i + 1]
        
        return ans

使用左右两次遍历来计算每个位置的答案，时间复杂度为 O(n)，且不使用除法：

python

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        # 初始化结果数组，每个位置初始为1
        answer = [1] * n

        # 从左往右遍历，answer[i] 存储的是 nums[0] 到 nums[i-1] 的乘积
        prefix = 1
        for i in range(n):
            answer[i] = prefix
            prefix *= nums[i]

        # 从右往左遍历，同时维护后缀乘积，将两部分相乘得到最终结果
        suffix = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= suffix
            suffix *= nums[i]

        return answer


# 测试用例
if __name__ == "__main__":
    sol = Solution()
    print(sol.productExceptSelf([1, 2, 3, 4]))  # 输出: [24, 12, 8, 6]
    print(sol.productExceptSelf([-1, 1, 0, -3, 3]))  # 输出: [0, 0, 9, 0, 0]

初始化:
使用 answer 数组保存最终结果，初始值均为 1。
第一次遍历（计算前缀乘积）:
定义变量 prefix 用来存储从起点到当前下标之前所有数字的乘积。
在遍历过程中，将当前 prefix 值赋给 answer[i]，然后更新 prefix 为 prefix * nums[i]。
第二次遍历（计算后缀乘积并更新结果）:
定义变量 suffix 用来存储从数组末尾到当前下标之后所有数字的乘积。
从数组末尾开始遍历，每个位置的最终答案等于前缀乘积（已存储在 answer[i] 中）乘以当前的后缀乘积 suffix。
随后更新 suffix 为 suffix * nums[i]。
这种方法满足 O(n) 的时间复杂度，并且仅使用了常数级额外空间（不计输出数组）。

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

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