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，得到每个每个元素的前缀积
pre = [1, 1, 2, 6] - 接着从后往前计算后缀积，最后一个元素的后缀积设置为1
post = [24, 12, 4, 1] 前缀积 * 后缀积对应项相乘得到最后的输出
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