<div>
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
<pre>Input: nums = [1,2,3,4] Output: [24,12,8,6] </pre>
Example 2:
<pre>Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0] </pre>
Constraints:
2 <= nums.length <= 10<sup>5</sup>-30 <= nums[i] <= 30- The product of any prefix or suffix of
numsis guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1)extra space complexity? (The output array does not count as extra space for space complexity analysis.)
</div>
题目大意：
求每个数对应的结果： 数组出自己外全部相乘
解题思路：
累计思想
解题步骤：
N/A
注意事项：
- 两轮计算，从左到右，再从右到左，用res数组作为临时计算结果。从左到右，计算res[i] = num[0] x nums[i - 1], 从右到左类似
- res初始值为1，因为从左到右是跳过第0个值的，而从右到左中res[i] *= product，若初始为0，结果res[i] = 0
Python代码：
1
2
3
4
5
6
7
8
9
10
11def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
res, product = [1] * n, nums[0]
for i in range(1, n):
res[i] = product # [1, 1]
product *= nums[i]
product = nums[-1] # 2
for i in range(n - 2, -1, -1):
res[i] *= product # [2, 1]
product *= nums[i]
return res
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
若可以用除法算法II解题思路：
按照定义用数学方法，但只要注意一个0和两个0的情况
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18def productExceptSelf(self, nums: List[int]) -> List[int]:
product, zero_count = 1, 0
for n in nums:
if n != 0:
product *= n
else:
zero_count += 1
if zero_count > 1:
return [0] * len(nums)
res = []
for i in range(len(nums)):
if nums[i] == 0:
res.append(product)
elif zero_count > 0:
res.append(0)
else:
res.append(int(product / nums[i]))
return res
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
