238. Product of Array Except Sel

问题描述

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Note: Please solve it without division and in O(n).
Follow up: Could you solve it with constant space complexity?

思路

假设一个list = [1,2,3],则我们的思路是，先想像出一个更坐标横坐标，走坐标都是这个list的矩阵。

矩阵中的数字，表明在return list，即ans中，各个位置都是什么的乘积。观察可得，改matrix大致被分成上下三角形两个部分。ans中某个位置的乘积则是这个位置的上下三角列乘积

    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ans = [1] * len(nums)
        left = 0
        right = len(nums)-1
        lp = rp = 1
        while left < len(nums)-1:
            lp *= nums[left]
            rp *= nums[right]
            ans[left + 1] *= lp
            ans[right - 1] *=rp
            left += 1
            right -= 1
        return ans