238. 除自身以外数组的乘积
题目描述
给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
算法
题中明确要求不能使用除法，本可以使用O(n^2)的双for暴力循环求解，但又要求在 O(n) 时间复杂度内。这就需要开动下脑筋，先来分析一下输出是怎么的得到：
24 = 2 * 3* 4
12 = 1 * 3 4
8 = 1 2 * 4
6 = 1 * 2 *3
记保存输出的向量为vec，长度为length。
显然vec[i]上需要填的值 = 前i个数累乘 * 后(length – i – 1)个数累乘
仔细一思考，这个好像可以和动态规划有些关联，毕竟涉及到前i个、后几个连乘这样的关系。现在还处在探索问题的阶段，将问题分为两部分思考，一个是从前往后走，一个是从后往前走，保存它们的累乘结果到2个数组中（先不考虑进阶部分要求的常数空间复杂度），观察这2个数组和我们最终的输出有什么关联。
从前往后
| nums | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| dp_forward | 1 | 1 | 2 | 6 |
if i > 0:
dp[i] = (nums[0]到nums[i-1]的累乘)
else:
dp[0] = 1
"""
dp数组的前后值有这么一个数学关系：
dp[i] = dp[i-1] * nums[i-1]
"""从后往前
为了方便阅读与理解，将nums反转为{4,3,2,1}。套用上面得到的数学关系，可以很轻松的到下面的结果：
| nums | 4 | 3 | 2 | 1 |
|---|---|---|---|---|
| dp_backward | 1 | 4 | 12 | 24 |
将nums反转为正常顺序{1,2,3,4}，表格变为：
| nums | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| dp_backward | 24 | 12 | 4 | 1 |
最后一步
我们已经得到从前向后累乘与从后向前累乘的各个位置上的结果，将它们放在一起：
| nums | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| dp_forward | 1 | 1 | 2 | 6 |
| dp_backward | 24 | 12 | 4 | 1 |
答案呼之欲出，将dp_forward和dp_backward一行对应相乘得到{24,12,8,6}正是需要的输出。
我敢保证这不是偶然，让我们在分析一遍下面这个式子：
vec[i] = 前i个数累乘 * 后(length – i – 1)个数累乘
前i个数累乘正好保存在dp_forward[i]中；同理，后(length – i – 1)个数累乘正好保存在dp_backward[i]中。正因为这样，所以对应相乘，才正好是需要的答案。
进阶部分
在常数空间复杂度内完成这个题目。 出于对空间复杂度分析的目的，输出数组不被视为额外空间。
也就是说，我们最多可以使用一个大小为length的数组外加几个常数这么多的存储空间。
我的想法是从前往后这部分一定要保存在输出数组中，后面从后往前这部分可以直接更新在输出数组中。具体不在赘述，看代码里的注释更好理解。
代码
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int length = nums.size();
// 输出数组
vector<int> vec(length, 1);
/*** 两次遍历，从前往后一次，从后往前一次 ***/
// 从前往后
int mul = 1;
for (int i = 1; i < length; i++)
{
mul *= nums[i-1];
vec[i] = mul;
}
// 从后往前
mul = 1;
for (int i = length - 2; i >= 0; i--)
{
mul *= nums[i+1];
// 更新在输出数组上，觉得抽象可以动笔画一画
vec[i] *= mul;
}
return vec;
}
};