Leetcode 238. Product of Array Except Self
思路：题目中说不能用除法；用暴力，会超时。
为了计算 除第i个元素的乘积，可以将数组分为三个部分：1...i-1; i; i+1...n (注：这里的i代表序号，不是数组下标)
output[i] = a * b[被乘数a：代表前i-1个数的乘积；乘数b：代表后n-i个数的乘积；output代表最后输出的结果]
所以之类求出a和b就可以了，求a和b的方法用累乘法。
nums: [1, 2, 3, 4];
nums1:[1, 1, 2, 6] (a[i]代表原数组nums左边i-1个数的乘积) nums1[i] = nums1[i-1] * nums[i-1] (i从1 -> n-1)
nums2:[24, 12, 4, 1](b[i]代表原数组nums右边n-i个数的乘积) nums2[i] = nums2[i+1] * nums[i+1](i从n-2到0)
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
nums1 = [1] * len(nums)
nums2 = [1] * len(nums)
for i in range(1, len(nums)):
nums1[i] = nums1[i-1] * nums[i-1]
print(nums1)
for i in range(len(nums)-2, -1, -1):
nums2[i] = nums2[i+1] * nums[i+1]
print(nums2)
prod = [1] * len(nums)
for i in range(len(nums)):
prod[i] = nums1[i] * nums2[i]
# prod = [1] * len(nums) #为了节省时间，可以将prod的计算放在求nums2的循环中。
# for i in range(len(nums)-2, -1, -1):
# nums2[i] = nums2[i+1] * nums[i+1]
# prod[i] = nums1[i] * nums2[i]
# prod[-1] = nums1[-1] * nums2[-1]
return prod
作者：想要成为大牛的李同学
