LC 238除了自身以外数组的乘积Product of Array Except Self　中等

返回结果数组，使每项等于除自身以外全部元素的乘积，不使用除法。

思路 前缀积×后缀积：先正向写入左侧积，再逆向乘上右侧积，输出数组即答案。时间 O(n)、额外空间 O(1)。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [1] * n
        pre = 1
        for i in range(n):  # ans[i] = 左侧前缀积
            ans[i] = pre
            pre *= nums[i]
        suf = 1
        for i in range(n - 1, -1, -1):  # 乘右侧后缀积
            ans[i] *= suf
            suf *= nums[i]
        return ans