2025/10/16

思路：回溯法，从不完全的一个因子也没有开始，一点点加因子，试探，找一个列表存这些部分乘积，如果与前面算重复了，就不探索。算到目标（n缺第i乘积的）的时候，就存到answer[i]里面。因为可以剪枝，所以是 $O (n)$ 。

评价：完全错误，回溯法没法降到 $O (n)$

推荐答案：左右两部分，1到i-1，i+1到n。前缀积从左往右扫一遍算完，后缀积从右往左扫一遍算完，最后i从1到n扫一遍拼接

2025/10/19

def productExceptSelf(self, nums: list[int]) -> list[int]:
    if nums == []: return []
    N = len(nums)
    left_product = [nums[0]]* N 
    right_product = [nums[-1]] * N
    results = [0] * N
    for i in range(1, N):
        left_product[i] = left_product[i-1] * nums[i]
        right_product[i] = right_product[-i-1] * nums[-i-1]
    results[0] = right_product[N-1]
    results[N-1] = right_product[N-1]
    for i in range(1, N):
        results[i] = left_product[i-1] * right_product[N - i - 1]
    return results