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

題目描述：

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

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

請(qǐng)?不要使用除法，且在?O(n)?時(shí)間復(fù)雜度內(nèi)完成此題。

示例 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ù)范圍內(nèi)

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

方法一思路分析：

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

代碼實(shí)現(xiàn)：

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

方法二思路分析：

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

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

舉一個(gè)具體的例子來(lái)說(shuō)明：

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

1. 計(jì)算每個(gè)元素左側(cè)所有元素的乘積：

   • 初始化結(jié)果數(shù)組?answer = [0, 0, 0, 0]。
   • answer[0]?設(shè)置為 1，因?yàn)榈谝粋€(gè)元素左側(cè)沒(méi)有其他元素。
   • 計(jì)算?answer[1]：answer[1] = nums[0] * answer[0] = 1 * 1 = 1。
   • 計(jì)算?answer[2]：answer[2] = nums[1] * answer[1] = 2 * 1 = 2。
   • 計(jì)算?answer[3]：answer[3] = nums[2] * answer[2] = 3 * 2 = 6。

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

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

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

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

代碼實(shí)現(xiàn)：

class Solution {public int[] productExceptSelf(int[] nums) {int length = nums.length;int[] answer = new int[length];// answer[i] 表示索引 i 左側(cè)所有元素的乘積// 因?yàn)樗饕秊?'0' 的元素左側(cè)沒(méi)有元素， 所以 answer[0] = 1answer[0] = 1;for (int i = 1; i < length; i++) {answer[i] = nums[i - 1] * answer[i - 1];}// R 為右側(cè)所有元素的乘積// 剛開(kāi)始右邊沒(méi)有元素，所以 R = 1int R = 1;for (int i = length - 1; i >= 0; i--) {// 對(duì)于索引 i，左邊的乘積為 answer[i]，右邊的乘積為 Ranswer[i] = answer[i] * R;// R 需要包含右邊所有的乘積，所以計(jì)算下一個(gè)結(jié)果時(shí)需要將當(dāng)前值乘到 R 上R *= nums[i];}return answer;}
}