给出一个数组nums，输出同样长度的数组，每个元素值为该数组所有数字的乘积除以nums[i]，要求不用除法
先从左到右扫一遍算prefix product，再从后向左扫一遍算suffix product
1 #576
2 #Runtime: 177 ms (Beats 26.93%)
3 #Memory: 17.4 MB (Beats 96.45%)
4
5 class Solution(object):
6 def productExceptSelf(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: List[int]
10 """
11 t = 1
12 ans = []
13 for i in xrange(len(nums)):
14 ans.append(t)
15 t *= nums[i]
16 t = 1
17 for i in xrange(len(nums) - 1, -1, -1):
18 ans[i] *= t
19 t *= nums[i]
20 return ans
21