题目

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:
输入: [1,2,3,4]
输出: [24,12,8,6]

提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

说明: 请不要使用除法，**且在 除自身以外数组的乘积 - 图1 时间复杂度内完成此题。

方案一

  1. class Solution:
  2.     def productExceptSelf(self, nums: List[int]) -> List[int]:
  3.         if not nums or len(nums) == 1:
  4.             return nums
  6.         left = [1] * len(nums)
  7.         for i in range(len(nums) - 1):
  8.             left[i + 1] = left[i] * nums[i]
  10.         right = [1] * len(nums)
  11.         for i in range(len(nums) - 2, -1, -1):
  12.             right[i] = right[i + 1] * nums[i + 1]
  14.         return [left[i] * right[i] for i in range(len(nums))]
  • 我们不必将所有数字的乘积除以给定索引处的数字得到相应的答案，而是可以利用索引处左侧的所有数字乘积和右侧所有数字的乘积相乘得到答案。

算法：

  1. 初始化两个空数组 L 和 R。对于给定索引 i，L[i] 代表的是 i 左侧所有数字的乘积，R[i] 代表的是 i 右侧所有数字的乘积。
  2. 填充 L 和 R 数组的值。
  3. 当 R 和 L 数组填充完成，我们只需要在输入数组上迭代，且索引 i 处的值为：L[i]*R[i]。

空间复杂度为除自身以外数组的乘积 - 图2的算法请参考第二个参考链接。

参考链接

https://leetcode-cn.com/explore/interview/card/2020-top-interview-questions/280/array/1254/
https://leetcode-cn.com/problems/product-of-array-except-self/solution/chu-zi-shen-yi-wai-shu-zu-de-cheng-ji-by-leetcode/