算法：除自身以外数组的乘积_算法除自身以外数组的乘积

如题：
对于一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
要求：不要使用除法，且在 O(n) 时间复杂度内完成此题。
题解：
要求1：不能使用除法，那只能相乘，例如对于nums = 【1,2,3,4】这样一个数组，求 0 号位的值，则只能使用nums[1]*nums[2]*nums[3]
要求2：在O（n）时间内，则不可以嵌套循环。
所以解法如下：

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        l = [nums[0]]
        size = len(nums)
        if size == 0:
            return 0
        # 求从左边开始递增的乘积
        r = [nums[size-1]]
        for index in range(1,size-1):
            multipy = l[index-1]*nums[index]
            l.append(multipy)
        # 求从右边开始递减的乘积
        for index in range(size-2,0,-1):
            multipy = r[size-2-index]*nums[index]
            r.append(multipy)
        # 用index左边递增的乘积 * 右边递减的乘积
        res = [r[-1]]
        for index in range(1,size-1):
            multipy = l[index-1]*r[size-2-index]
            res.append(multipy)
        res.append(l[-1])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24