1.題目介紹
????????給定一個整數數組?nums，返回 數組?answer?，其中?answer[i]?等于?nums?中除?nums[i]?之外其余各元素的乘積?。
題目數據?保證?數組?nums之中任意元素的全部前綴元素和后綴的乘積都在??32 位?整數范圍內。
請?不要使用除法，且在?O(n)?時間復雜度內完成此題。
2 <= nums.length <= 105-30 <= nums[i] <= 30- 輸入?保證?數組?
answer[i]?在??32 位?整數范圍內
2.解決思路
? ? ? ? 既然給定一個數組，讓求得每個位置的前綴元素和后綴元素的乘積，實際上就是分別求前綴積和后綴積。我一開始的思路是：如果每次計算前綴積和后綴積的時候都遍歷一遍就太浪費時間了，所以就想著如何減少遍歷次數，也就是利用前面遍歷過的結果，我就想到了“后一個元素的前綴積=前一個元素的前綴積*前一個元素”，這樣就可以做到前綴積無需遍歷，只需要每次相乘即可。但是這樣的問題是由于是從前向后計算，那么后綴積其實是沒辦法通過這種方式得到的，只能遍歷計算，最終時間復雜度還是O(n2)。
? ? ? ? 所以換一種思路?，能不能在計算的時候直接取到前綴積和后綴積，所以可以直接提前進行兩次計算，分別計算每個位置的前綴積和后綴積，結合上面的思路，計算前綴積和后綴積的過程都只需要一次遍歷即可。最終拿著這兩個數組按位置相乘就是最終的答案
3.步驟講解
? ? ? ? 1.先對一些特殊情況進行提前處理
? ? ? ? 2.創建前綴積數組和后綴積數組，分別用來存儲每個位置的前綴積或者后綴積
? ? ? ? 3.初始化結果數組
? ? ? ? 4.計算前綴乘積，第一個位置的前綴積為1，后面每個位置的前綴積都是上一個前綴積*上一? ? ? ? ? ? ? ?個元素值
? ? ? ? 5.計算后綴乘積，從后向前計算。最后一個位置的后綴積為1，后面每個位置的前綴積都是后? ? ? ? ? ? ? 一個后綴積*后一個元素值。
? ? ? ? 6.計算每個位置的前綴積*后綴積，也就是通過索引取得前綴積數組和后綴積數組相乘
4.代碼展示
public static int[] test2(int[] nums) {int n = nums.length;if (n == 0) return new int[0];if (n == 1) return new int[]{0};// 創建前綴乘積和后綴乘積數組int[] prefix = new int[n];int[] suffix = new int[n];//結果數組int[] results = new int[n];// 計算前綴乘積prefix[0] = 1;for (int i = 1; i < n; i++) {prefix[i] = prefix[i - 1] * nums[i - 1];}// 計算后綴乘積suffix[n - 1] = 1;for (int i = n - 2; i >= 0; i--) {suffix[i] = suffix[i + 1] * nums[i + 1];}// 計算結果for (int i = 0; i < n; i++) {results[i] = prefix[i] * suffix[i];}return results;}5.執行結果
在leetcode中測試用例平均耗時2ms
內存分布55.04MB?
?
超時代碼示例（O(n2)）：
public static int[] test(int[] nums) {if (nums.length == 0){return new int[0];}if (nums.length == 1){return new int[]{0};}//先計算所有元素的前綴乘和后綴乘int tempPreMulti = 1;int tempSufMulti = 1;int[] results = new int[nums.length];HashMap<Integer, Integer[]> multi = new HashMap<>();for (int i = 0; i < nums.length; i++) {//計算前綴乘if (i != 0) {tempPreMulti = multi.get(i - 1)[0] * nums[i - 1];}//計算后綴乘for (int j = i+1; j < nums.length; j++) {tempSufMulti *= nums[j];}multi.put(i, new Integer[]{tempPreMulti, tempSufMulti});//存入數組results[i] = tempPreMulti*tempSufMulti;//重置tempSufMulti = 1;tempPreMulti = 1;}return results;}
)
)
