## Sunday, October 25, 2015

### [Leetcode] Product of Array Except Self, Solution

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]`.
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.)
[Thoughts]

`output[i]` is equal to the product of all the elements of `nums` except `nums[i]`.

output[i] =  { i 前面的数的乘积}  X  { i 后面的数的乘积}

[Code]
``````1:  class Solution {
2:  public:
3:    vector<int> productExceptSelf(vector<int>& nums) {
4:      vector<int> products;
5:      if(nums.size() == 0) return products;
6:      int product = 1;
7:      products.push_back(1);
8:      for(int i =1; i< nums.size(); i++) {
9:        product *= nums[i-1];
10:        products.push_back(product);
11:      }
12:      product = 1;
13:      for(int i =nums.size()-2; i>=0; i--) {
14:        product = product * nums[i+1];
15:        products[i] = products[i] * product;
16:      }
17:      return products;
18:    }
19:  };
``````

github: https://github.com/codingtmd/leetcode/blob/master/src/Product%20of%20Array%20Except%20Self.cpp