在原始森林

题目

https://leetcode.cn/problems/product-of-array-except-self/

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

自解

看到时间复杂度我就傻了，有思路但是暴力解

暴力解

def productExceptSelf(self, nums: List[int]) -> List[int]:
    multple = []
    for i in range(len(nums)):
        temp=1
        for j in range(len(nums)):  
            if j!=i:
                temp=temp*nums[j]
        multple.append(temp)
    return multple 

左右乘积列表- O(n) 时间复杂度

利用索引左侧所有数字的乘积和右侧所有数字的乘积（即前缀与后缀）相乘得到答案。

1. 初始化两个空数组 L 和 R。对于给定索引 i，L[i] 代表的是 i 左侧所有数字的乘积，R[i] 代表的是 i 右侧所有数字的乘积。
2. 需要用两个循环来填充 L 和 R 数组的值。对于数组 L，L[0] 应该是 1，因为第一个元素的左边没有元素。对于其他元素：L[i] = L[i-1] * nums[i-1]。
3. 同理，对于数组 R，R[length-1] 应为 1。length 指的是输入数组的大小。其他元素：R[i] = R[i+1] * nums[i+1]。[]
4. 当 R 和 L 数组填充完成，我们只需要在输入数组上迭代，且索引 i 处的值为：L[i] * R[i]

def productExceptSelf(self, nums: List[int]) -> List[int]:
    L=[0] * len(nums)
    R=[0] * len(nums)
    M=[0] * len(nums)
    for i in range(len(nums)):
        if i == 0:
            L[i]=1
        else:
            L[i]=L[i-1]*nums[i-1] 
    for i in range(len(nums)-1,-1,-1):
        if i == len(nums)-1:
            R[len(nums)-1]=1
        else:
            R[i]=nums[i+1]*R[i+1]
    for i in range(len(nums)):
        M[i]=L[i]*R[i]
    return M

看着思路写的代码

1. 没定义数组长度，然后用索引赋值报错“list assignment index out of range”
2. range () 是左开右闭的！
3. 数组初始化的方法

题解

定义 pre[i] 表示从 nums[0] 到 nums[i−1] 的乘积，前缀积。

定义 suf[i] 表示从 nums[i+1] 到 nums[n−1] 的乘积，即后缀积。
先计算 suf，然后一边计算 pre，一边把 pre 直接乘到 suf[i] 中。最后返回 suf。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        suf = [1] * n
        for i in range(n - 2, -1, -1):
            suf[i] = suf[i + 1] * nums[i + 1]
        pre = 1
        for i, x in enumerate(nums):
            # 此时 pre 为 nums[0] 到 nums[i-1] 的乘积，直接乘到 suf[i] 中
            suf[i] *= pre
            pre *= x
        return suf

这个方法优化了空间。

后缀积 suf 如何计算索引。应该考虑临界情况，如果在最后一位计算，右边没有任何数，应该固定为 1。于是我们从倒数第二位开始计算，且 range 是左闭右开的，因此 (n - 2, -1，-1)，表示从倒数第二位倒着跳到索引为 0 。