Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

思路

题目要我们求出数组除了当前元素以外的所有数的乘积，不能使用除法，并使用O(n)的时间复杂度。经过一番……很长时间的考虑，也没想出来。

实际上是一个典型的空间换时间的方法，从左往右记录该元素以左（不含该元素）的累乘结果；再从右向左做一次。最后的结果是两组结果对应的乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        left = []
        right = []
        ans = []
        product = 1
        for i in nums:
            left.append(product)
            product *= i
        
        product = 1
        for i in nums[::-1]:
            right.append(product)
            product *= i
        
        print left
        print right
        
        length = len(nums)
        for i in range(length):
            ans.append(left[i] * right[length-1-i])
        
        return ans