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

题目：

给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

分析：
本来最简单的做法是遍历一遍数组，拿到总乘积，然后再遍历一遍，用除法就搞定了。这种方式最简单也最有效，但是题目偏偏不让。

按照最暴力的解法，遍历数组拿到当前的数后，再去遍历数组里其余的数，一个一个乘积得到结果。但是这样太暴力了，时间复杂度太高 ，O(n*n)

所以需要思考如何其他解法？

如上面的数组，如果遍历到3的时候，我们知道的是3之前的乘积，但是3之后的乘积是不清楚的。
所以如果知道了3之后的乘积，就能把一切问题解决了。
3之后的乘积如何获取？貌似我们可以倒序遍历一次，就可以知道了。

为了减少如暴力法的多次循环，可以先倒序遍历一次，用表存下来后面所有的乘积。

代码如下：

class Solution:
        
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        tempDic,index,afterNum = {},1,1
        tempDic[0] = 1
# 倒序获取剩余部分的乘积，存入字典里
# 字典存的是剩余几个的乘积。比如tempDic[2] = 10,就代表数组右边剩余2个元素的乘积。
        for num in reversed(nums):
            afterNum *= num
            tempDic[index] = afterNum
            index +=1
        result,afterNum,totalLen = [],1,len(nums)
# 正序遍历，用afterNum存左边的乘积，从字典里拿右边的乘积。相乘获取结果存入数组
        for currentIndex in range(totalLen):
            result.append(afterNum*tempDic[totalLen-currentIndex-1])
            afterNum *= nums[currentIndex]
        return result