Product of Array Except Self
你会得到一个整数数组 nums。返回一个长度相同的数组 answer，其中 answer[i] 是 nums 中除索引 i 处元素之外所有元素的乘积。要求在 O(n) 时间内完成，且不使用除法。
函数
- numsinteger-array
- 整数数组，且至少包含两个元素
- 返回值integer-array
- 一个数组，其中索引 i 处的值是除 nums[i] 以外所有元素的乘积
约束条件
2 ≤ nums.length ≤ 104-30 ≤ nums[i] ≤ 30- 所有非零
nums值的乘积可以用 32 位有符号整数表示，因此你在计算过程中得到的每个乘积也都可以用 32 位有符号整数表示。
示例
- 输入
- nums = [2, 3, 4, 5]
- 输出
- [60, 40, 30, 24]
- 解释
- 去掉 2 后，剩下 3 × 4 × 5 = 60。用同样的方法，去掉 3、4 或 5 后，结果分别是 40、30 和 24。
- 输入
- nums = [-2, 5, 0, 3]
- 输出
- [0, 0, -30, 0]
- 解释
- 每个包含 0 的乘积都是 0。只有索引 2 对应的乘积不包含 0，它是 -2 × 5 × 3 = -30。
- 输入
- nums = [0, 4, 0, -1]
- 输出
- [0, 0, 0, 0]
- 解释
- 有两个 0 时，每个乘积都至少包含其中一个 0，所以答案中的每个值都是 0。
进阶
你能否只使用 O(1) 的额外空间，不计你返回的数组？
提示
逐个打开提示，每个都会多透露一点。
对每个索引，把其他所有值相乘是可行的，但有 10,000 个值时，大约需要进行 1 亿次乘法，其中大多数都是重复的。索引
i对应的乘积和索引i + 1对应的乘积有什么共同点？除了
nums[i]以外的所有值，分成它左边的值和右边的值。如果你知道每个前缀和每个后缀的乘积，那么每个答案只需进行一次乘法。从左侧开始，用每个索引之前的值的乘积填充答案数组，初始值为 1。然后从右侧遍历，用一个累积乘积记录索引之后的值：先将它乘入答案，再乘入
nums[i]。
题解
除 nums[i] 以外所有数的乘积，等于它左侧所有值的乘积乘以右侧所有值的乘积。通过前缀积和后缀积，只需遍历两次就能算出所有结果，而且不需要除法，因此无需对零值做特殊处理。输出数组可以存储左侧的乘积，再用一个变量存储右侧的乘积。
将其他值分别与每个索引相乘
结果正确，但无法在最大的测试中运行完毕
思路
对于每个索引 i，先将乘积设为 1，然后将所有 j 不等于 i 的 nums[j] 乘进去。跳过索引 i，而不是之后再除掉它，可以避免零带来的问题。每个位置需要进行 n-1 次乘法，当 n = 10^4 时约为 10^8 次；相邻索引的乘积除了两个值外，其余值都相同。
算法
- 创建一个长度为 n 的答案数组。
- 对于每个索引
i，将product设为 1。 - 将每个索引
j不等于i的nums[j]乘到product上。 - 将
product存储在答案数组的索引i处。 - 返回答案。
def productExceptSelf(nums):
n = len(nums)
answer = []
for i in range(n):
product = 1
for j in range(n):
if j != i:
product *= nums[j]
answer.append(product)
return answer前缀和后缀乘积数组
思路
把索引 i 之前各个值的乘积记为 before[i]，把它之后各个值的乘积记为 after[i]。然后 answer[i] = before[i] × after[i]，这样就不用除法，而且会跳过 nums[i]。
每个数组都通过与相邻值相乘来逐步构建。before[0] 为 1，表示没有任何值的乘积；before[i] = before[i-1] × nums[i-1]；after 则从右端开始以相同方式构建。对于 [2, 3, 4, 5]，得到 before = [1, 2, 6, 24] 和 after = [60, 20, 5, 1]，它们对应位置的乘积为 [60, 40, 30, 24]。这两个辅助数组需要额外的 O(n) 内存。
算法
- 从左向右填充
before：before[0] = 1，然后每一项都等于前一项乘以前一个值。 - 从右向左填充
after：after[n-1] = 1，然后每一项都等于后一项乘以后一个值。 - 对每个索引，将
answer[i]设为before[i] × after[i]。 - 返回
answer。
def productExceptSelf(nums):
n = len(nums)
# before[i] = product of nums[0..i-1], after[i] = product of nums[i+1..n-1]
before = [1] * n
after = [1] * n
for i in range(1, n):
before[i] = before[i - 1] * nums[i - 1]
for i in range(n - 2, -1, -1):
after[i] = after[i + 1] * nums[i + 1]
return [before[i] * after[i] for i in range(n)]答案中左边的乘积，一个正在运行的右边乘积
思路
从右端开始遍历时，索引 i 之后的值的乘积是一个数字，所以你不需要整个 after 数组。把它保存在变量 right 中，并在每一步用一次乘法更新它。
将左侧乘积直接写入答案数组。反向遍历时，先用 right 乘以 answer[i]，再用 nums[i] 乘以 right：在索引 i 处使用 right 时，它还不能包含 nums[i]。对于 [2, 3, 4, 5]，在索引 3、2、1 和 0 处，right 分别是 1、5、20 和 60。除了返回的数组外，额外内存只需一个变量。
算法
- 将
answer[0] = 1，然后从左到右设置answer[i] = answer[i-1] × nums[i-1]。 - 将
right设为 1。 - 从最后一个索引到 0，将
answer[i]乘以right。 - 然后将
right乘以nums[i]。 - 返回
answer。
def productExceptSelf(nums):
n = len(nums)
# Pass 1: answer[i] = product of everything left of i
answer = [1] * n
for i in range(1, n):
answer[i] = answer[i - 1] * nums[i - 1]
# Pass 2: multiply in the product of everything right of i
right = 1
for i in range(n - 1, -1, -1):
answer[i] *= right
right *= nums[i]
return answer
易错点和边界情况
- 用总乘积除以
nums[i]。对于[-2, 5, 0, 3]，总乘积是 0，而索引 2 处需要计算 0 除以 0。 - 在使用
right之前，先将它乘以nums[i]，这样nums[i]就会被计入自身的乘积。对于[2, 3, 4, 5]，最后一个值会变成 120，而不是 24。 - 将左侧乘积的初始值设为
nums[0]，而不是 1。索引 0 左侧没有元素，所以它的左侧乘积是 1；否则，对于[2, 3, 4, 5]，索引 0 处的结果会是 120，而不是 60。 - 循环边界。左侧遍历会读取
nums[i-1]，所以从索引 1 开始；后缀数组会读取nums[i+1]，所以从索引 n-2 开始。
常见问题3
除自身以外数组的乘积的时间复杂度是多少？
前缀和后缀的解法只需 O(n) 时间，从两端各遍历一次。将左侧的乘积存入输出数组，再用一个不断更新的右侧乘积，除输出数组外只需 O(1) 的额外空间。对每个索引都计算其他所有值的乘积，则需要 O(n²) 时间。
为什么“除自身以外数组的乘积”不允许使用除法？
当数组中包含 0 时，将乘积总值除以 nums[i] 会出错：乘积总值为 0，而 0 所在的索引需要除以 0。要修复这个问题，需要统计 0 的数量并处理特殊情况。前缀积和后缀积无需特殊处理就能应对 0。
输出数组算额外空间吗？
不。无论如何你都必须返回答案，因此按照通常的约定，不把它计入空间复杂度。把左侧的乘积存储在其中，并把右侧的乘积存储在一个变量中，额外空间复杂度算作 O(1)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def productExceptSelf(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [2, 3, 4, 5]
预期输出
[60, 40, 30, 24]