優質博文：IT-BLOG-CN

一、題目

給你一個整數數組nums，返回數組answer，其中answer[i]等于nums中除nums[i]之外其余各元素的乘積。題目數據保證數組nums之中任意元素的全部前綴元素和后綴的乘積都在32位整數范圍內。請不要使用除法，且在O(n)時間復雜度內完成此題。

示例 1:
輸入: nums = [1,2,3,4]
輸出: [24,12,8,6]

示例 2:
輸入: nums = [-1,1,0,-3,3]
輸出: [0,0,9,0,0]

2 <= nums.length <= 105
-30 <= nums[i] <= 30
保證數組nums之中任意元素的全部前綴元素和后綴的乘積都在32位整數范圍內

進階：你可以在O(1)的額外空間復雜度內完成這個題目嗎？（ 出于對空間復雜度分析的目的，輸出數組 不被視為 額外空間。）

二、代碼

【1】創建左右乘積列表： 我們不能將所有數字的乘積除以給定索引處的數字得到相應的答案，而是利用索引左側所有數字的乘積和右側所有數字的乘積（即前綴與后綴）相乘得到答案。初始化兩個數組Left和Right，對于指定的下表i，left[i]代表i左側所有數據的乘積，right[i]代表i右側所有數據的乘積。我們利用循環將數據填充到lfet[]和right[]數組中，然后將left[i]和right[i]相乘就是i的左右乘積。

class Solution {public int[] productExceptSelf(int[] nums) {if (nums == null || nums.length == 0) {return null;}// 我們使用數組，也就是當前數字的left[] 和 right[] 數組，分別存儲左右兩邊的和;int len = nums.length;int res[] = new int[len];int left[] = new int[len];int right[] = new int[len];// 第一個數之前的數的乘積為1，所以先給個默認值left[0] = 1;for (int i = 1; i < len; i++) {// left 中保存的是i之前所有數的乘積left[i] = left[i - 1] * nums[i - 1];}// 最有邊的數也保存為1right[len - 1] = 1;for (int i = len - 2; i >= 0; i--) {right[i] = right[i + 1] * nums[i + 1];}for (int i = 0; i < len; i++) {res[i] = left[i] * right[i];}return res;}
}

時間復雜度： O(N)，其中N指的是數組nums的大小。預處理L和R數組以及最后的遍歷計算都是O(N)的時間復雜度。
空間復雜度： O(N)，其中N指的是數組nums的大小。使用了L和R數組去構造答案，L和R數組的長度為數組nums的大小。

【2】空間復雜度O(1)的方法： 由于輸出數組不算在空間復雜度內，那么我們可以將L或R數組用輸出數組來計算。先把輸出數組當作L數組來計算，然后再動態構造R數組得到結果。

class Solution {public int[] productExceptSelf(int[] nums) {if (nums == null || nums.length == 0) {return null;}// 因為返回的數組可以不算在空間復雜度中，所以可以作為臨時變量存放left[]數據int len = nums.length;int res[] = new int[len];// // 第一個數之前的數的乘積為1，所以先給個默認值res[0] = 1;for (int i = 1; i < len; i++) {// left 中保存的是i之前所有數的乘積res[i] = res[i - 1] * nums[i - 1];}// 然后從后向前變量，通過變量 right保存前幾位數的乘積int right = 1;for (int i = len - 1; i >= 0; i--) {res[i] *= right;// 放在返回值的后面，就相當于i + 1right *= nums[i];} return res;}
}

時間復雜度： O(N)，其中N指的是數組nums的大小。分析與方法一相同。
空間復雜度： O(1)，輸出數組不算進空間復雜度中，因此我們只需要常數的空間存放變量。