238. Product of Array Except Self

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Constraint: It’s guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

---

很有意思的一个题。给定一个数组，要求数组中除了当前元素的其他所有元素的乘积。比如数组[1,2,3,4]，则3对应的值应该是1*2*4=8。
题目要求不能用除法，且要是常数时间空间复杂度。
如果能用除法就很简单了，先把数组完整的乘积算出来，然后依次除以每个元素。
网上看了题解，这题还是很巧妙的。我们可以扫描两遍数组，第一遍从左往右，计算不包括当前元素的之前所有元素的乘积；第二遍从右往左，计算不包括当前元素的之后所有元素的乘积；最后把两遍的结果乘起来就是要求的结果。比如样例
原始数组    1,  2, 3, 4
第一遍        1,  1, 2, 6
第二遍     24, 12, 4, 1
两遍乘积 24, 12, 8, 6
仔细想想很容易就知道其中的原理，对于第i个元素，最终结果应该是
$(x_0*x_1*…*x_{i-1})*(x_{i+1}*x_{i+2}*…*x_{n-1})$
第一遍相当于计算了前半部分，第二遍相当于计算了后半部分，最后两个部分乘起来就好了。
题目还有一个要求，就是常数空间复杂度，方法是：第二遍的时候，借助一个变量right_prod来存储从右到左的乘积，ans里面就是第二遍乘第二遍的结果，也就是最终结果。
完整代码如下：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        vector<int> ans(nums.size(), 1);
        for (int i = 1; i < nums.size(); i++) {
            ans[i] = ans[i – 1] * nums[i – 1];
        }
        int right_prod = 1;
        for (int i = nums.size() – 2; i >= 0; i–) {
            right_prod *= nums[i + 1];
            ans[i] *= right_prod;
        }
        return ans;
    }
};

本代码提交AC，用时52MS。