📘 題目敘述
給定一個整數陣列 nums，請回傳一個陣列 answer，其中 answer[i] 代表：
nums中除了nums[i]以外所有元素的乘積
題目要求：
- 不能使用除法（題目原本的進階要求）
- 並且演算法需在
O(n)時間內完成
（我的寫法有用除法，但我先把題目需求完整寫在這裡）
條件限制
2 ≤ nums.length ≤ 10^5-30 ≤ nums[i] ≤ 30- 保證任意前綴或後綴的乘積都在 32-bit 整數範圍內
🧠 解題思路（一）
我這份程式的核心想法是：
- 先把「所有非 0 的數字」乘起來，得到一個總乘積
pd - 然後用
pd去算每一個位置「除了自己以外的乘積」
但是這題最麻煩的地方其實是 0，因為：
- 只要陣列中有 0，乘積會整個變成 0
- 如果直接做除法
pd / nums[i]，遇到nums[i] = 0也會出錯
所以我的邏輯主要是在分情況處理「0 的數量」。
所有變數
n：陣列nums的長度pd：把所有「非 0 元素」乘起來的乘積zero：是否已經遇到過 0（用來判斷 0 的數量）zpos：若只有一個 0，記錄那個 0 出現的位置answer：答案陣列（我先初始化為全 0，方便處理多個 0 的情況）
🪜 主要流程步驟
第一階段：掃描整個陣列，統計 0 的情況並計算乘積
我用一次迴圈掃過 nums：
情況一：遇到 nums[i] == 0
- 如果我之前已經遇過 0（
zero == true），代表陣列裡至少有兩個 0
這種情況下，不管你排除哪一個元素，剩下的乘積裡一定還有 0，所以答案一定是：
- 每一格都是 0
因此我直接回傳已經是全 0 的 answer。
情況二：第一次遇到 0
- 把
zero設成true - 把
zpos記錄成目前位置
同時我不把 0 乘進 pd（避免整個乘積變成 0）。
情況三：遇到非 0 的數字
- 我把它乘進
pd - 因為
pd代表的是「所有非 0 的總乘積」
第二階段：根據 0 的數量決定怎麼填答案
情況一：陣列中剛好只有一個 0（zero == true）
這時候只有 zpos 那個位置的答案會是非 0：
answer[zpos] =「所有非 0 的乘積」=pd
原因是：
- 對於
zpos位置：排除掉 0 之後，剩下全都是非 0，所以乘積是pd - 對於其他位置：你排除的是非 0，但剩下仍包含那個 0，所以乘積一定是 0
而我一開始把 answer 初始化成全 0，所以只要補 zpos 這格就好。
情況二：陣列中完全沒有 0（zero == false）
這時候我就可以用最直覺的方式：
answer[j] = pd / nums[j]
因為：
pd是所有元素的乘積- 除掉
nums[j]就得到「除了自己以外的乘積」
💡 整體邏輯總結
- 兩個以上的 0 → 全部答案都是 0
- 剛好一個 0 → 只有 0 的位置是
pd，其他都 0 - 沒有 0 → 用總乘積
pd直接除掉自己
這樣可以在 O(n) 時間內完成，而且邏輯非常直觀。
💻 程式碼實作
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
int pd = 1, zpos;
bool zero = false;
vector<int> answer(n, 0);
for (int i = 0; i < n; i++) {
if (nums[i] == 0) {
if (zero) {
return answer;
} else {
zero = true;
zpos = i;
}
} else {
pd = pd * nums[i];
}
}
if (zero) {
answer[zpos] = pd;
return answer;
}
for (int j = 0; j < n; j++) {
answer[j] = pd / nums[j];
}
return answer;
}
};
🧠 解題思路（二）（但會TLE）
我後來想到的做法是：
- 先把
answer初始化成全部都是1 - 然後對每個位置
j，把「所有不是j的元素」都乘進去
我的寫法是用兩層迴圈去完成：
- 外層固定某個元素
nums[i] - 內層跑過所有位置
j，只要i != j，就把nums[i]乘到answer[j]
這樣做的效果就是：
- 對於每個
j，我會把除了nums[j]以外的所有數字都乘進answer[j]
所有變數
n：陣列nums的長度answer：答案陣列，一開始全部設成1i：外層迴圈正在看的元素索引j：內層迴圈正在更新的答案位置
🪜 主要流程步驟
第一步：初始化答案陣列
- 建立
answer，長度為n - 每一格都先放
1，因為乘法的單位元素是1
第二步：雙迴圈把元素乘進去
外層：走過每個 nums[i]
我把 nums[i] 當成「等一下要乘進去的某一個因數」。
內層：走過每個答案位置 answer[j]
- 如果
j != i，代表answer[j]的乘積應該包含nums[i] - 所以執行
answer[j] *= nums[i]
為什麼這樣會 TLE
因為我用了兩層迴圈：
- 外層跑
n次 - 內層也跑
n次
所以總操作次數大約是：n * n = O(n^2)。
而題目給的 n 最大可以到 10^5，10^5^2 = 10^10 次操作，這個數量級一定會超時。
因此這個方法雖然直觀、也很好理解，但不符合題目要求的 O(n)。
💻 程式碼實作
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> answer(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
answer[j] *= nums[i];
}
}
}
return answer;
}
};
🔗 題目連結
https://leetcode.com/problems/product-of-array-except-self/