238. 除自身以外数组的乘积 Medium
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
解题思路
输入： 一个整数数组 nums
输出： 返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外所有元素的乘积
思路分析
本题属于 前缀积 + 后缀积 的典型问题。
由于题目要求 不能使用除法，我们可以利用前缀积和后缀积：
- 前缀积：
prefix[i]表示nums[0..i-1]的乘积 - 后缀积：
suffix[i]表示nums[i+1..n-1]的乘积
那么答案就是：
answer[i] = prefix[i] * suffix[i]空间优化技巧
为了节省空间，可以不用单独开后缀数组：
第一次遍历计算前缀积，直接存放在
answer[i]中。第二次遍历时，用一个变量
suffix维护当前位置右侧所有元素的乘积，并不断更新：answer[i] *= suffix suffix *= nums[i]
这样就能在 O(n) 时间、O(1) 额外空间（不计输出数组）的条件下完成计算。
代码实现
python
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums) # 获取数组长度
ans = [1] * n # 初始化结果数组，长度为 n，所有元素初始为 1
# 初始化前缀乘积为 1
prefix = 1
# 先计算当前数字的前缀之积
for i in range(n):
# 当前结果数组中的第 i 个元素乘以前缀积
ans[i] *= prefix
# 更新前缀乘积，乘上当前 nums[i] 值
prefix *= nums[i]
# 初始化后缀乘积为 1
suffix = 1
# 再将当钱数字的前缀积乘后缀积就是结果
for j in range(n - 1, -1, -1): # 从右往左遍历
# 当前结果数组中的第 j 个元素乘以后缀积
ans[j] *= suffix
# 更新后缀乘积，乘上当前 nums[j] 值
suffix *= nums[j]
return ans # 返回最终的结果数组javascript
/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function(nums) {
// 初始化结果数组，长度与 nums 相同，初始值全部为 1
const ans = Array(nums.length).fill(1);
// 第一步：计算前缀积
// ans[i] 存放 nums[0..i-1] 的乘积（即 i 左边所有元素的积）
for (let i = 1; i < nums.length; i++) {
ans[i] = ans[i - 1] * nums[i - 1];
}
// 第二步：计算后缀积并与前缀积相乘
// suffix 表示当前位置右边所有元素的乘积，初始值为 1（表示空积）
let suffix = 1;
for (let j = nums.length - 1; j >= 0; j--) {
// ans[j] 已经是左边所有元素的积，再乘上右边所有元素的积（suffix）
ans[j] *= suffix;
// 更新 suffix，为下一个位置准备
suffix *= nums[j];
}
// 返回结果数组
return ans;
};复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)