Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/

第一次循环，建立left数组和right数组，通过动态规划来压缩时间复杂度。

第二次循环，直接通过left和right数组相乘得到结果，并直接返回到res数组

 1 class Solution {
 2 public:
 3     vector<int> productExceptSelf(vector<int>& nums) {
 4         int size=nums.size();
 5         vector<int> res;
 6         if(size==0)
 7             return res;
 8         if(size==1)
 9         {
10             res.push_back(0);
11             return res;
12         }
13         int * left=new int[size];
14         int * right=new int[size];
15         int leftVal=1;
16         int rightVal=1;
17         for(int i=0;i<size;i++)
18         {
19             if(i==0)
20             {
21                 left[i]=1;
22                 right[size-1-i]=1;
23             }
24             else
25             {
26                 leftVal=leftVal*nums[i-1];
27                 left[i]=leftVal;
28                 rightVal=rightVal*nums[size-i];
29                 right[size-i-1]=rightVal;
30             }
31         }
32         for(int i=0;i<size;i++)
33         {
34             int temp=left[i]*right[i];
35             res.push_back(temp);
36         }
37         return res;
38     }
39 };