前言

今天这道题是中等难度的

题目

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

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

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

示例 1:

示例 2:

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

**进阶：**你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

分析

这道题其实如果没限制，上来就是相乘，然后除以当前元素。然而即使没有限制，这个方案也有个大问题：不能和0相除。

所以我们要另外想办法，给的是一维的数组，那么理论上时间复杂度可以是O(n)。

但是按题目的要求，处理每个元素的时间都得是O(n)，即每个answer[i]都需要nums.all来计算。

实际上这里面是存在重复的，比如第一个元素和第二个元素相乘，后面n-2个元素都是会重复计算这俩的，就像斐波那契一样，前面一堆其实都是重复的，这个时候我们其实可以借助类似dp的记录功能。

那么要怎么记录呢？我们先来分析下每个元素自身的answer，比如第二个元素，它是第一个元素和第三个 - 第n个元素相乘的结果，也就是nums2前面和后面相乘的结果，那么如果我们可以先知道这前面和后面的结果不就很好处理了吗，并且因为前面都是重复的所以不需要去重复的生成。

既然有两部分，那么我们就需要知道前面部分和后面部分的相乘结果，最后再把他俩相乘，那么就是最终结果，即left_dp[i] = left_dp[i - 1] * nums[i - 1], right_dp[i] = right_dp[i + 1] * nums[i + 1]（右边是从右往左计算的）

ok，豁然开朗。

我们先左边来一波，然后再右边来一波，预处理完毕之后再遍历然后left_dp[i] * right_dp[i]即可。

实际时间复杂度为O(3n)，3可以忽略。

解

进阶分析

我们上面用了left_dp和right_dp，空间复杂度为O(n)

直接基于nums是不可能的，但是我们可以放到answer里。

和上面差不多，我们先过一波左边。右边就不能这么做了，因为此时right_dp[i + 1]也就是answer[i + 1]是已经成型的了，说人话就是：已经是最终结果了。我们不能拿这个值再来算，所以我们还需要有一个变量用来存储right_dp[i + 1]的值。

进阶解

测试用例

总结

后面类似这种预处理的还有很多，这题主要是告诉我们O(xn)只要x是常数，那也算O(n)。所以有的时候我们需要第i个元素后面的值，不妨尝试下预处理的方案。