LeetCode 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]

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.)

解析：

计算除了当前元素之外的数组中其他元素的乘积。要求返回结果是result数组，result[i]的结果为nums数组中除第i个元素之外的其他元素乘积。要求不能使用出发，并且要求O(n)的时间复杂度。条件随机场中计算一个序列的概率值时会用到前向、后向算法，可以用在此处解决问题。每个元素之前所有元素的乘积和元素之后所有元素的乘积即为所求结果，因此定义两个数组，分别存放当前元素之前的所有元素乘积结果，和当前元素之后所有元素乘积结果。代码如下：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        vector<int> forward(len, 1);//定义前向数组
        vector<int> backward(len, 1);//定义后向数组
        vector<int> result(len, 0);
        for(int i =0; i < len-1; i++)//依次计算前向数组结果
        {
            forward[i+1] = forward[i] * nums[i];
        }
        for(int i=len-1; i > 0; i--)//依次计算后向数组结果
        {
            backward[i-1] = backward[i]*nums[i];
        }
        for(int i=0; i < len; i++)
        {
            result[i] = forward[i] * backward[i];
        }
        return result;
    }
};