[238] Product of Array Except Self

其實我不知道這題發生了什麼事, 我需要抽根菸冷靜先～（山頂吹風）

看了別人的圖解好像有懂了那麼一點點, 但是也只有一點點><

乘過去再乘回來, 然後呢><!!! 

為什麼最後再兩個相乘一次就是解答了呢為什麼呢~~~>< 

還有什麼prefix sum 我怎麼從來沒聽過！！！大驚！！！（抱頭!!!)

/**

 * 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) {

    int *left = malloc(sizeof(int)*numsSize);

    int *right = malloc(sizeof(int)*numsSize);

    *returnSize=numsSize;

    left[0]=1;

    for (int i=1;i<numsSize;i++)

        left[i]=left[i-1]*nums[i-1];

    right[numsSize-1]=1;

    for(int j=numsSize-2;j>=0;j--)

        right[j]=right[j+1]*nums[j+1];

    for (int i=0;i<numsSize;i++)

        left[i]=left[i]*right[i];

    return left;

}