題目：除自身外數組的乘積

????????給你一個整數數組 nums，返回 數組 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘積 。

題目數據保證數組 nums之中任意元素的全部前綴元素和后綴的乘積都在 32 位 整數范圍內。

請不要使用除法，且在 O(n) 時間復雜度內完成此題。

提示：

?2 <= nums.lengh <= 10^5

-30 <= nums[i] <= 30

保證數組之中任意元素的全部前綴元素和后綴的乘積都在 32 位 整數范圍內 nums；

示例 1:

輸入：nums=[ 1，2，3，4 ]

輸出：[ 24，12，8，6 ]

示例 2:

輸入：nums=[ -1，-1，0，-3，3 ]

輸出：[ 0，0，9，0，0 ]

解題思路：

定義兩個數組（前綴乘積數組與后綴乘積數組），前綴數組為：left [ ] ，后綴數組：right [ ] ;

left [ i ] 里存 nums [ i ] 前面的乘積和，righ[ i ] 里存 nums [ i ] 后面的乘積和，(為空時存1)；

創建一個動態內存變量 int* ret=(int*)malloc(sizeof(int)*numsSize);

然后ret [ i ]=left [ i ] * right [ i ]，存儲后返回；

思路實現：

因為數組元素 ：2 <= nums.lengh <= 10^5

所以前綴和后綴數組申請的數組大小都是10^5;

int left[100000]={0};
int right[100000]={0};

然后就是遍歷求前綴乘積數組的各項值：

    //前綴乘積和for(i=0;i<numsSize;i++){if(i==0){left[i]=1;}else{left[i]=left[i-1]*nums[i-1];}}

解析：

這里呢用數組 nums?[ 1，2，3，4，5，6 ] 來舉例；?

此時，left [ 0 ] =1，然后 left [ 1 ] = left [ 0 ] * nums [ 0 ]? 相當于?left [ 1 ] = nums [ 0 ] ;

left [ 2 ] = left [ 1 ] * nums [ 1 ]? 相當于 left [ 2 ] = nums [ 0 ] * nums [ 1 ] ;

left [ 3?] = left [ 2?] * nums [ 2?]? 相當于 left [ 3?] = nums [ 0 ] * nums [ 1 ] * nums [ 2?] ;

。。。。。。

left [ 5?] = left [ 4?] * nums [ 4?]? 相當于 left [ 5?] = nums [ 0 ] * nums [ 1 ] * nums [ 2?] *?nums [ 3?] * nums [ 4?] ；

想必大家也已經找到其中的規律了；

然后就是遍歷求后綴乘積數組的各項值：

   //后綴乘積和for(i=numsSize-1;i>=0;i--){if(i==numsSize-1){right[i]=1;}else{right[i]=right[i+1]*nums[i+1];}}

解析：

同理：nums?[ 1，2，3，4，5，6 ]

left [ 5?] =1，然后 left [ 4?] = left [ 5 ] * nums [ 5?]? 相當于?left [ 4?] = nums [ 5?] ;

left [ 3?] = left [ 4?] * nums [ 4?]? 相當于 left [ 3?] = nums [ 4?] * nums [ 5?] ;

left [ 2?] = left [ 3?] * nums [ 3?]? 相當于 left [ 2?] = nums [ 3?] * nums [ 4?] * nums [ 5?] ;

。。。。。。

left [ 0?] = left [ 1?] * nums [ 1?]? 相當于 left [ 0?] = nums [ 1?] * nums [ 2?] * nums [ 3?] *?nums [ 4?] * nums [ 5?] ；

然后就是給返回值（* returnSize）賦值，以及創建動態內（ret），以及給其賦值再返回；

    * returnSize=numsSize;int* ret=(int*)malloc(4*numsSize);//給返回指針賦值for(i=0;i<numsSize;i++){ret[i]=left[i]*right[i];}

時間復雜度為（O(N) ) ；

這就是這道題目的基本思路，下面是程序源代碼：

int* productExceptSelf(int* nums, int numsSize, int* returnSize){int i=0;int left[100000]={0};int right[100000]={0};//前綴乘積和for(i=0;i<numsSize;i++){if(i==0){left[i]=1;}else{left[i]=left[i-1]*nums[i-1];}}//后綴乘積和for(i=numsSize-1;i>=0;i--){if(i==numsSize-1){right[i]=1;}else{right[i]=right[i+1]*nums[i+1];}}* returnSize=numsSize;int* ret=(int*)malloc(4*numsSize);//給返回指針賦值for(i=0;i<numsSize;i++){ret[i]=left[i]*right[i];}return ret;
}

如有不足歡迎來補充交流！

完結。。。

---

????????