除自身以外數(shù)組的乘積

題目描述：

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

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

請?不要使用除法，且在?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
• 保證?數(shù)組?nums之中任意元素的全部前綴元素和后綴的乘積都在??32 位?整數(shù)范圍內

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

方法一思路分析：

1. 初始化左右乘積數(shù)組：
   • 創(chuàng)建兩個輔助數(shù)組?L?和?R，長度與輸入數(shù)組?nums?相同。L[i]?用于存儲?nums[i]?左側所有元素的乘積，R[i]?用于存儲?nums[i]?右側所有元素的乘積。
2. 計算左側乘積：
   • 初始化?L[0]?為 1，因為第一個元素左側沒有元素。
   • 從左到右遍歷?nums，計算每個位置的左側乘積并存儲在?L?數(shù)組中。
3. 計算右側乘積：
   • 初始化?R[length - 1]?為 1，因為最后一個元素右側沒有元素。
   • 從右到左遍歷?nums，計算每個位置的右側乘積并存儲在?R?數(shù)組中。
4. 計算最終結果：
   • 創(chuàng)建一個結果數(shù)組?answer，長度為?nums?的長度。
   • 對于?nums?中的每個元素，其除了自身以外所有元素的乘積就是其左側所有元素的乘積乘以右側所有元素的乘積。即?answer[i] = L[i] * R[i]。
5. 返回結果：
   • 返回?answer?數(shù)組作為最終結果。

代碼實現(xiàn)：

class Solution {public int[] productExceptSelf(int[] nums) {int length = nums.length;// L 和 R 分別表示左右兩側的乘積列表int[] L = new int[length];int[] R = new int[length];int[] answer = new int[length];// L[i] 為索引 i 左側所有元素的乘積// 對于索引為 '0' 的元素，因為左側沒有元素，所以 L[0] = 1L[0] = 1;for (int i = 1; i < length; i++) {L[i] = nums[i - 1] * L[i - 1];}// R[i] 為索引 i 右側所有元素的乘積// 對于索引為 'length-1' 的元素，因為右側沒有元素，所以 R[length-1] = 1R[length - 1] = 1;for (int i = length - 2; i >= 0; i--) {R[i] = nums[i + 1] * R[i + 1];}// 對于索引 i，除 nums[i] 之外其余各元素的乘積就是左側所有元素的乘積乘以右側所有元素的乘積for (int i = 0; i < length; i++) {answer[i] = L[i] * R[i];}return answer;}
}

方法二思路分析：

????????題目進階要求在?O(1)?的額外空間復雜度內完成這個題目，且輸出數(shù)組不算額外空間。所以可以考慮用一個變量代替數(shù)組的使用，變量為右側所有元素的乘積。

1. 計算每個元素左側所有元素的乘積：
   • 創(chuàng)建一個與原數(shù)組相同長度的新數(shù)組?answer，用于存儲結果。
   • 初始化?answer[0]?為 1，因為第一個元素左側沒有其他元素。
   • 從第二個元素開始遍歷原數(shù)組，每個位置?i?的?answer[i]?等于?nums[i - 1]?乘以?answer[i - 1]。這樣，answer[i]?就存儲了原數(shù)組中索引?i?左側所有元素的乘積。
2. 計算每個元素右側所有元素的乘積，并更新結果數(shù)組：
   • 初始化一個變量?R?為 1，用于存儲當前元素右側所有元素的乘積。
   • 從原數(shù)組的最后一個元素開始向左遍歷。
   • 對于每個元素，將其左側乘積（即?answer[i]）與右側乘積?R?相乘，得到的結果就是除了?nums[i]?以外的所有元素的乘積，并更新?answer[i]。
   • 更新?R，將其乘以當前遍歷到的元素?nums[i]，以便計算下一個元素的右側乘積。

舉一個具體的例子來說明：

假設我們有一個整數(shù)數(shù)組?nums = [1, 2, 3, 4]。

1. 計算每個元素左側所有元素的乘積：

   • 初始化結果數(shù)組?answer = [0, 0, 0, 0]。
   • answer[0]?設置為 1，因為第一個元素左側沒有其他元素。
   • 計算?answer[1]：answer[1] = nums[0] * answer[0] = 1 * 1 = 1。
   • 計算?answer[2]：answer[2] = nums[1] * answer[1] = 2 * 1 = 2。
   • 計算?answer[3]：answer[3] = nums[2] * answer[2] = 3 * 2 = 6。

   此時，answer = [1, 1, 2, 6]。這個數(shù)組存儲了每個元素左側所有元素的乘積。

2. 計算每個元素右側所有元素的乘積，并更新結果數(shù)組：

   • 初始化變量?R = 1，用于存儲當前元素右側所有元素的乘積。
   • 從右向左遍歷?nums?數(shù)組。
   • 對于?nums[3]（即 4）：answer[3] = answer[3] * R = 6 * 1 = 6，然后?R = R * nums[3] = 1 * 4 = 4。
   • 對于?nums[2]（即 3）：answer[2] = answer[2] * R = 2 * 4 = 8，然后?R = R * nums[2] = 4 * 3 = 12。
   • 對于?nums[1]（即 2）：answer[1] = answer[1] * R = 1 * 12 = 12，然后?R = R * nums[1] = 12 * 2 = 24。
   • 對于?nums[0]（即 1）：answer[0] = answer[0] * R = 1 * 24 = 24。

   最終，answer = [24, 12, 8, 6]。這個數(shù)組就是除了自身以外所有元素的乘積。

代碼實現(xiàn)：

class Solution {public int[] productExceptSelf(int[] nums) {int length = nums.length;int[] answer = new int[length];// answer[i] 表示索引 i 左側所有元素的乘積// 因為索引為 '0' 的元素左側沒有元素， 所以 answer[0] = 1answer[0] = 1;for (int i = 1; i < length; i++) {answer[i] = nums[i - 1] * answer[i - 1];}// R 為右側所有元素的乘積// 剛開始右邊沒有元素，所以 R = 1int R = 1;for (int i = length - 1; i >= 0; i--) {// 對于索引 i，左邊的乘積為 answer[i]，右邊的乘積為 Ranswer[i] = answer[i] * R;// R 需要包含右邊所有的乘積，所以計算下一個結果時需要將當前值乘到 R 上R *= nums[i];}return answer;}
}