LEET code --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].

用除法一下就寫完
麻煩的是要怎麼只用乘法做完
每個答案都可以看成是  {某個數字的左邊所有乘積*某個數字的右邊所有乘積}
EX:
以3來說    左邊所有乘積是1*2，右邊所有乘積是4，最後可以兩者相乘得出答案

因此 可以先計算出所有的左邊累積乘積，最後從後面開始回頭算出右邊乘積
兩者相乘可以得出答案

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

/** * Return an array of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */ int* productExceptSelf(int* nums, int numsSize, int* returnSize) { *returnSize=numsSize; int *LeftAccum=(int*)malloc(sizeof(int)*numsSize); LeftAccum[0]=1; for(int i =1;i<numsSize;i++){ LeftAccum[i] = nums[i-1]*LeftAccum[i-1]; } int right=1; for(int i=numsSize-1;i>=0;i--){ LeftAccum[i]*=right; right*=nums[i]; } return LeftAccum; }