Leetcode-238.除自身以为的数组相乘

用两个prefix和suffix记录前后缀的乘积

class Solution:

    def productExceptSelf(self, nums: List[int]) -> List[int]:

        n=len(nums)

        answer=[1]*n

        prefix = 1

        for i in range(n):

            answer[i]=prefix

            prefix*=nums[i]

        suffix = 1

        for j in  range(n-1,-1,-1):

            answer[j]=answer[j]*suffix

            suffix*=nums[j]

        return answer

注意：题目限制复杂度了，所以不能使用双循环，本题巧妙的地方在于，用了前缀积和后缀积储存该数组前后的乘积。注意上部分的循环和下部分循环有轻微不一样，就是下部分的循环直接乘answer即可保证了连贯。

空间复杂度分析的标准约定：

在算法分析中，空间复杂度指的是“额外使用的空间”，不包括输入和输出所占用的空间。这是因为：

• 输入和输出是你无论如何都必须要有的。

• 空间复杂度衡量的是：你为了解决这个问题，额外用的内存是多少。

所以：

• 如果你要返回一个长度为 n 的数组 answer，那这个空间是题目要求必须有的，不算在“额外空间”中；

• 只有那些你为了计算结果而额外创建的辅助结构才算