給定一個數組 A[0,1,…,n-1]，請構建一個數組 B[0,1,…,n-1]，其中 B[i] 的值是數組 A 中除了下標 i 以外的元素的積, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

示例:

輸入: [1,2,3,4,5]
輸出: [120,60,40,30,24]

提示：

所有元素乘積之和不會溢出 32 位整數
a.length <= 100000

解題思路

1. 維護兩個數組，一個是正向累乘的數組pos[i]表示A[1]* A[2] * …A[i]的值，另一個是逆向累乘的數組neg[i]表示A[i]* A[i+1] *…A[n-1]的值
2. 因此B[i]=pos[i-1]*neg[i+1]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]

代碼

class Solution {public int[] constructArr(int[] a) {int n=a.length;if (n<=1) return a;int[] pos = new int[n],neg=new int[n],res=new int[n];pos[0]=a[0];neg[n-1]=a[n-1];for (int i=1;i<n;i++)pos[i]=a[i]*pos[i-1];for (int i=n-2;i>=0;i--)neg[i]=a[i]*neg[i+1];res[0]=neg[1];res[n-1]=pos[n-2];for (int i=1;i<n-1;i++)res[i]=pos[i-1]*neg[i+1];return res;}
}