238. Product of Array Except Self

发表于 | 分类于 | |

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

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

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

主要就是预处理。把数组预先正序和逆序都累乘一遍，这样针对某个nums[i]，只需要将其前面的正序积和其后面的逆序积相乘就可以得到答案了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//
// Created by chaopengz on 2017/11/1.
//

#include "head.h"

class Solution {
public:
    vector<int> productExceptSelf(vector<int> &nums)
    {
        int len = (int) nums.size();
        vector<int> ans;
        vector<int> fromBegin;
        vector<int> fromEnd;
        int sumBegin = 1, sumEnd = 1;
        fromBegin.push_back(1);
        fromEnd.push_back(1);
        for (int i = 0; i < len; ++i)
        {
            sumBegin *= nums[i];
            sumEnd *= nums[len - 1 - i];
            fromBegin.push_back(sumBegin);
            fromEnd.push_back(sumEnd);
        }
        for (int j = 0; j < len; ++j)
        {
            ans.push_back(fromBegin[j] * fromEnd[len - j - 1]);
        }
        return ans;
    }
};