LeetCode238.除自身以外数组的乘积

题目大意

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

思路分析

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

这个题可以使用列表元素的总积除当前元素得到输出列表的每个项，但是可惜题目不让用。
扩展另一个概念，前缀积&后缀积。例如，对于index=1的输出来说，其输出值8就是nums[2]的前缀积2*后缀积4。所以说我们只需要计算当前nums元素的前缀积和后缀积即可得到输出列表的每一项。

拿示例1来说：

1. 第一个元素的前缀积设置为1，得到每个每个元素的前缀积
   pre = [1, 1, 2, 6]
2. 接着从后往前计算后缀积，最后一个元素的后缀积设置为1
   post = [24, 12, 4, 1]
3. 前缀积 * 后缀积对应项相乘得到最后的输出
   out = [1*24, 1*12, 2*4, 6*1] = [24, 12, 8, 6]

代码实现中，前缀和后缀都可以在一个列表中实现

代码示例

Java版本

class Solution {public int[] productExceptSelf(int[] nums) {int l = nums.length;int [] res = new int[l];int pre = 1;for(int i=0; i<l; i++){res[i] = pre;pre *= nums[i];}int post = 1;for(int i=l-1; i>-1; i--){res[i] *= post;post *= nums[i];}return res;}
}

Python版本

class Solution:def productExceptSelf(self, nums: List[int]) -> List[int]:# 前缀积res = [1] * len(nums)pre = 1for i in range(len(nums)):# 这样写也可以# res[i] = nums[i-1] * res[i-1] if i > 0 else 1res[i] = prepre *= nums[i]#  & 后缀积post = 1for i in range(len(nums)-1, -1, -1):res[i] *= postpost *= nums[i]return res