解法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年。
