238. 除自身以外數組的乘積

中等

給你一個整數數組 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 輸入 保證 數組 answer[i] 在 32 位 整數范圍內

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

思路：分別計算每個元素的 左側元素的乘積 and 右側元素的乘積

關鍵: 每個元素的左右乘積如何記錄下來？常規做法是可以開兩個數組left[nums.size]、right[nums.size]記錄.但仔細觀察后可以發現這里每個元素的左右側乘積是連續的. 也就是第i個元素的左乘積 = 第 i - 1 元素的左乘積 * 第 i - 1個元素, 可使用一個變量記錄上一個元素的左乘積得到. 同理可以計算右乘積

class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] answer = new int [n];// 初始化每個元素的左右乘積int left = 1;int right = 1;for(int i = 0; i < n; i ++){answer[i] = 1;}
?// 先將所有元素的左乘積給計算出來for(int i = 0; i < n; i ++){// 第i個元素的左乘積 = 第 i - 1 元素的左乘積 * 第 i - 1 個元素answer[i] = left;// 計算第 i + 1 個元素的左乘積left *= nums[i];}
?// 再計算右乘積, 與左乘積同理, 對稱for(int i = n - 1; i >= 0; i --){//不同的是先計算了左乘積(此時answer中保存了每個元素的左乘積), 所以需要用右乘積乘上左乘積, 這里為 *=answer[i] *= right;right *= nums[i];}return answer;}
}