问题描述：

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

解题思路：

从输出的数组可以看出：

[2*3*4, 1*3*4, 1*2*4, 1*2*3]。输出的数组下标位置，是原数组以该下标为基准，分为左右两边，左边的积乘右边的积的结果。即：

output[index] = P1(index-1) * P2(index + 1); 

P1(x)为0到x的乘积；P2(x)为x到原数组结尾的乘积。

时间复杂度分析：

用两个数组分别存储P1和P2的结果，复杂度为O(n)。依次算出输出数组对应下标的结果，复杂度为O(n)。因此，结果复杂度为O(n)。

空间复杂度分析：

用输出数组来存P1的值，原数组空间存P2。没有开辟复杂度O(n)的数组。因此空间复杂度是O(1)，即一些临时变量。

源码：

class Solution {

public:

vectorproductExceptSelf(vector& nums) { 

 int index = 0, length = nums.size(); 

 int num[length], arr1[length], arr2[length]; 

 for(int i = 0; i < length; ++ i) { 

 int temp = i == 0 ? 1 : arr1[i - 1]; 

 arr1[i] = temp * nums[i]; 

 } 

 for(int i = length - 1; i >= 0; -- i) { 

 int temp = (i == length - 1) ? 1 : arr2[i + 1]; 

 arr2[i] = temp * nums[i]; 

 } 

 vector newVector;

  for(int i = 0; i < length; ++ i) {

  int temp_left = i == 0 ? 1 : arr1[i - 1],

  temp_right = i == length - 1 ? 1 : arr2[i + 1];

  newVector.push_back(temp_right * temp_left);

  }

  return newVector;

}

};