https://leetcode.cn/problems/product-of-array-except-self/description/

一、題目分析

給你一個整數數組?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]

? ? ? ? 結合題目以及示例，我們不難看出今天這道題目的需要完成的操作就是求出除自身以外的乘積，并存放到一個數組中，最后返回數組。

三、解題思路&代碼實現

? ? ? ? 在拿到任何一道題目的時候，我們首先要做的就是認真審題，讀懂題目要求以后，在心里或者草稿紙上寫出模擬過程的偽代碼，之后再做進一步的優化。今天這道題目也一樣，我們什么算法都先不要考慮，就用最暴力的方法來做。

1、暴力解法（復雜度為O(n^2)）

1、核心思路：對于每一個nums[i]，遍歷整個數組，跳過nums[i]并計算其余元素的乘積

?2、關鍵步驟：

? ? ? ? ?1、初始化ans數組，該數組的長度于nums數組相同

?????????2、雙重循環計算乘積：

? ? ? ? ? ? ? ? 外層循環：遍歷每個nums[i]，準備計算ans[i]。

? ? ? ? ? ? ? ? 內層循環：遍歷nums所有元素，遇到 i == j時跳出此次循環（排除自身），其余元素累乘到sum。

????????3、存儲結果：

? ? ? ? ? ? ? ? 將計算好的sum存入到ans[i]中。

vector<int> productExceptSelf(vector<int>& nums) {vector<int> ans(nums.size());  // 定義結果數組，長度與 nums 相同// 遍歷計算每個位置 ans[i] 的值for (int i = 0; i < nums.size(); i++) {long long sum = 1;  // 初始化乘積為 1（因為 1 不影響乘法結果）// 計算 nums 中除 nums[i] 外所有元素的乘積for (int j = 0; j < nums.size(); j++) {if (j == i) continue;  // 跳過當前元素 nums[i]，不參與乘積計算sum *= nums[j];  // 累乘其他元素}ans[i] = sum;  // 將計算結果存入 ans[i]}return ans;  // 返回最終結果
}

? ? ? ? 但是本題暴力解法是并不能通過所有的測試用例，題目的數據范圍給到了1e5，如果是雙重循環的話就是1e10。(PS:C/C++ 1秒能跑的數據大概是在1e7~1e8左右)。

? ? ? ? 那么現在就要想辦法優化把這段程序優化至O(n)；????????

2、分類討論（數學分類法）

? ? ? ? 數學分類法的核心思路：

????????首先要統計出數組中是否有零，如果有的話零有多少個，如果有且僅有一個的話，那么ans數組中的元素就應該是除nums數組元素中為0的那一個元素應該為其余元素的乘積，其他元素則全部為零。

? ? ? ? 如果nums數組中0的個數>1，那么ans數組中的所有元素都應為0；

? ? ? ? 除以上兩種情況外 也就是nums數組中沒有零。

1. 單零情況：若數組中僅含一個零，那么結果數組中，零所在位置的元素為其余非零元素的乘積，其余位置元素均為零。例如，對于數組?[1, 0, 2, 3]，結果數組為?[0, 6, 0, 0]，因為?1*2*3=6，零位置填充該值，其余位置補零。
2. 多零情況：當數組中零的數量大于 1 時，無論如何計算，乘積必然為零，因此結果數組的所有元素均為零。
3. 無零情況：若數組中不存在零，結果數組的每個元素等于數組所有元素的乘積除以對應位置的元素。例如，對于數組?[1, 2, 3, 4]，結果數組為?[24, 12, 8, 6]?，因為?1*2*3*4=24，分別除以?1、2、3、4?得到對應位置結果。

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {// 初始化結果數組，大小與輸入數組相同vector<int> ans(nums.size());// sum: 所有元素的乘積（初始為1）// cnt_0: 統計數組中0的個數int sum = 1, cnt_0 = 0;// 第一次遍歷：計算所有元素的乘積，并統計0的個數for (auto i : nums) {sum *= i;           // 累乘所有元素if (i == 0)         // 遇到0時計數cnt_0++;}// 情況1：數組中恰好有1個0if (cnt_0 == 1) {int sum = 1;  // 重新計算非0元素的乘積（避免之前sum=0的影響）// 計算所有非0元素的乘積for (int i = 0; i < nums.size(); i++) {if (nums[i] != 0)sum *= nums[i];}// 填充結果數組：// - 非0位置的結果為0（因為總乘積含0）// - 0位置的結果為非0元素的乘積for (int i = 0; i < nums.size(); i++) {if (nums[i] != 0)ans[i] = 0;elseans[i] = sum;}return ans;}// 情況2：數組中有超過1個0// 所有位置的結果都是0（因為任何位置都至少包含一個0）if (cnt_0 > 1) {return ans;  // ans已初始化為全0}// 情況3：數組中沒有0// 直接計算：ans[i] = 總乘積 / nums[i]for (int i = 0; i < nums.size(); i++) {ans[i] = sum / nums[i];}return ans;}
};

????????以上代碼是優化了時間復雜度，但是題目中也是有明確要求不能使用除法的，所以盡管我們這段代碼的時間復雜度已經優化至O(n)。但還是需要改進。

3、前綴和&后綴和思想（正解√）

? ? ? ??核心思想：

? ? ? ??此方法的核心思想就是空間換時間，利用前綴和的思想的對ans數組進行預處理，這樣的好處就是每次取一個結果所需的時間復雜度為常數級，也就是O(1)。

? ? ? ? 其次通過將目標乘積拆分為兩部分（左部分、右部分）。第一次看到這段代碼時候，應該會想為什么能把nums[i]排除呢？

• 左邊乘積（ans[i]）不包含?nums[i]（因為只乘到?nums[i-1]）。

• 右邊乘積（right）不包含?nums[i]（因為先乘?right，再更新?right）。

• 最終結果：ans[i] = 左邊乘積 × 右邊乘積，自然排除了?nums[i]。

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {// 初始化結果數組，所有元素初始值為1（乘法單位元）vector<int> ans(nums.size(), 1);// 第一次遍歷：計算每個元素左邊所有元素的乘積（前綴積）// ans[i] 表示 nums[0] × nums[1] × ... × nums[i-1]for (int i = 1; i < nums.size(); i++) {ans[i] = ans[i - 1] * nums[i - 1];  // 遞推計算前綴積}// 初始化右邊乘積為1（最右邊元素的右邊沒有元素）int right = 1;// 第二次遍歷（從右往左）：計算右邊乘積并合并到結果中// 此時 ans[i] = 左邊乘積 × 右邊乘積for (int i = nums.size() - 1; i >= 0; i--) {ans[i] *= right;   // 將當前元素的右邊乘積乘到結果上right *= nums[i];  // 更新右邊乘積（包含當前元素）}return ans;}
};

????????至此，上述代碼均滿足題目的所有要求！！！完結撒花🌸🌸🌸

四、題目總結

????????本題要求在不使用除法且時間復雜度為?O(n)?的條件下，計算數組中除自身元素之外其余各元素的乘積。解題過程需結合題目要求與數據限制，通過逐步優化算法來實現目標。

????????在暴力解法中，采用雙重循環遍歷數組，對每個元素計算其余元素的乘積，雖然邏輯直觀，但時間復雜度高達?O(n^2)，無法滿足題目數據范圍的要求。

????????數學分類法通過統計數組中零的數量進行分類討論，優化了時間復雜度至?O(n)。當數組中有一個零，結果數組中零位置為其余非零元素乘積，其余位置為零；若有多個零，結果數組全為零；若無零，則用所有元素乘積除以對應位置元素得到結果。然而，該方法使用了除法運算，不符合題目要求。

????????最終的前綴和與后綴和思想是本題正解。利用空間換時間，通過兩次遍歷分別計算前綴積和后綴積，將目標乘積拆分為左右兩部分。先從前向后計算前綴積存入結果數組，再從后向前更新后綴積并與前綴積合并，既避免了除法運算，又滿足了?O(n)?的時間復雜度要求，高效且準確地解決了問題 。這種解題過程體現了在算法設計中平衡時間復雜度、空間復雜度與題目限制條件的重要性。

????????算法之美在于其嚴謹的邏輯與精巧的設計。希望讀者能通過本題，掌握空間換時間的核心思想，在日后的開發中靈活運用這種預處理技巧。謝謝大家！！！荊軻刺秦！