題目
給定一個長度為 n 的整數陣列 nums ，其中 n > 1，返回輸出陣列 answer ，其中 answer[i] 等於 nums 中除 nums[i] 之外其餘各元素的乘積。
nums 的任何前綴或後綴的乘積都保證適合 32 位元整數。
題目限制在
O(n)時間複雜度內完成，且不能使用除法。
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 105-30 <= nums[i] <= 30- The product of any prefix or suffix of
numsis guaranteed to fit in a 32-bit integer.
解題思路
- 前綴積陣列（Prefix Product Array）：計算每個位置
i左側所有元素的乘積。 - 後綴積陣列（Suffix Product Array）：計算每個位置
i右側所有元素的乘積。
最終結果中的每個位置 i 的值將是對應位置的前綴積和後綴積的乘積。
前綴積陣列
nums: [2,4,1,3,5]
第一個元素為 2，除去 2 以外，其他元素的乘積恰好是後面四個元素的乘積，而後面四個元素的乘積就是 2 的後綴之積，根據 前綴之積*後綴之積 = 後綴之積 的公式可得出前綴之積為 1
第二個元素是4，前綴之積是 2 * 2 的前綴之積，也就是 1 * 2 = 2
然後是1，前綴之積是 4 * 4 的前綴之積，也就是 1 * 2 * 4 = 8
再來是3，前綴之積是 1 * 1 的前綴之積，也就是 1 * 2 * 4 * 1 = 8
最後是5，前綴之積是 3 * 3 的前綴之積，也就是 1 * 2 * 4 * 1 * 3 = 24
得出的前綴之積陣列為 L: [1,2,8,8,24]
後綴積陣列
後綴積也是同樣的求法，只不過是從陣列後面往前遍歷。
nums: [2,4,1,3,5]
最後一位元素是 5，除去 5 以外，其他元素的乘積恰好是前面四個元素的乘積，而前面四個元素的乘積就是 5 的前綴之積，根據 前綴之積*後綴之積 = 前綴之積 的公式可得出後綴之積為 1
第二個元素是3，後綴之積是 5 * 5 的後綴之積，也就是 1 * 5 = 5
然後是1，後綴之積是 3 * 3 的後綴之積，也就是 1 * 5 * 3 = 15
再來是4，後綴之積是 1 * 1 的後綴之積，也就是 1 * 5 * 3 * 1 = 15
最後是2，後綴之積是 4 * 4 的後綴之積，也就是 1 * 5 * 3 * 1 * 4 = 60
得出的後綴之積陣列為 R: [60,15,15,5,1]
求解
nums: [2,4,1,3,5] 得出前綴積陣列為 L: [1,2,8,8,24]，後綴積陣列為 R: [60,15,15,5,1]
那麼將前綴積和後綴積相乘就能得到答案，也就是 answer: [60, 30, 120, 40, 24]
- 時間複雜度：
O(n)3輪循環，其中 n 指的是 input 陣列的長度 - 空間複雜度：
O(n)2個陣列，使用了前綴積陣列和後綴積陣列去得到答案
進階：空間複雜度O(1)
Follow up: Can you solve the problem in
O(1)extra space complexity? (The output array does not count as extra space for space complexity analysis.)
最後題目進階問能否使用空間複雜度 O(1) 完成？ （輸出陣列不計入）
這代表我們不能用兩個陣列 L, R 來完成。
改進方式是第一輪循環直接使用 answer 來存儲前綴之積，第二輪循環求後綴之積 R 的過程不變，第三輪循環中直接將 answer 的對應元素乘以 R 的對應元素。
nums: [2,4,1,3,5]
answer: [1,2,8,8,24] * R: [60,15,15,5,1]
: [60, 30, 120, 40, 24]
第一輪循環：
1.answer 存儲每個元素的前綴之積
第二輪循環：
1.answer 更新為前綴之積和後綴之積的乘積
2.然後更新每個元素的後綴之積 R
如此一來便省了一輪循環，並且空間複雜度變為 O(1)完整程式碼
/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function(nums) {
let answer = new Array(nums.length).fill(0)
// 前綴積
answer[0] = 1
for (let i = 1; i < nums.length; i++) {
answer[i] = answer[i - 1] * nums[i - 1]
}
// 後綴積
let R = 1
for (let i = nums.length - 1; i >= 0; i--) {
answer[i] *= R
R *= nums[i]
}
return answer
};
