原题出处：https://leetcode.cn/leetbook/read/top-interview-questions-hard/xw8dz6/

解法一：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        L, R, answer = [0]*n, [0]*n, [0]*n
        
        # 计算左侧所有数字的乘积
        L[0] = 1
        for i in range(1, n):
            L[i] = L[i-1] * nums[i-1]
        
        # 计算右侧所有数字的乘积
        R[n-1] = 1
        for i in reversed(range(n-1)):
            R[i] = R[i+1] * nums[i+1]
            
        # 计算最终结果
        for i in range(n):
            answer[i] = L[i] * R[i]
        
        return answer

思路：使用前缀积和后缀积来解决，这样每个元素对应的答案就等于它的前缀积乘上后缀积。具体来说，我们可以先正向遍历一遍数组，对于每个位置 i，计算出 i 左侧所有数字的乘积，存入数组 L 中。然后再反向遍历一遍数组，对于每个位置 i，计算出 i 右侧所有数字的乘积，存入数组 R 中。最后对于每个位置 i，其对答案的 contrib[i] 就是 L[i-1] * R[i+1]。