解法1， 用一个list记录从左边开始除了自己的乘积，然后另一个list记录右边开始除了自己的乘积，然后把这辆list对应项乘起来就行。实际实现的时候右边的list可以用一个数代替节省一点空间
例子 1，没有0的情况
例子 2，有0的情况
思路其实和盛水题目有点像
时间 O(N)，空间 O(N)
Python代码
class Solution:
# @param {integer[]} nums
# @return {integer[]}
def productExceptSelf(self, nums):
l = len(nums)
ret = [1] * l
for i in range(1, l):
ret[i] = ret[i-1] * nums[i-1]
right = 1
for i in range(l-2, -1, -1):
right *= nums[i+1]
ret[i] *= right
return ret
解法2，根据0的情况分类。
如果没0，全部乘起来，然后再扫一遍，除以自己。
有一个0，把非0的乘起来，除了0的位置，其他全是0， 0的位置为其他非0的乘积。
有2个及以上的0，全部都是0
例子
时间 O(N)，空间 O(N)
Python
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
product = None
zero_index = None
zero_counts = 0
for i in xrange(len(nums)):
if product is None:
product = nums[i]
continue
if nums[i] != 0:
product *= nums[i]
else:
zero_counts += 1
zero_index = i
if zero_counts == 2:
break
if product is None:
return product
if zero_counts == 0:
products = [product / x for x in nums]
elif zero_counts == 1:
products = [0] * len(nums)
products[zero_index] = product
else:
products = [0] * len(nums)
return products做这题想到这俩解法相隔竟已5年。
