題目
給你一個整數數組 nums，返回 數組 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘積 。
題目數據 保證 數組 nums之中任意元素的全部前綴元素和后綴的乘積都在 32 位 整數范圍內。
請 不要使用除法，且在 O(n) 時間復雜度內完成此題。
一、代碼實現
func productExceptSelf(nums []int) []int {n := len(nums)answer := make([]int, n)// 計算左側乘積answer[0] = 1for i := 1; i < n; i++ {answer[i] = answer[i-1] * nums[i-1]}// 計算右側乘積并合并結果right := 1for i := n-1; i >= 0; i-- {answer[i] *= rightright *= nums[i]}return answer
}
二、算法分析
1. 核心思路
? 左右乘積分解：將每個位置的乘積拆分為左側所有元素的乘積和右側所有元素的乘積的積。
? 空間優化：復用輸出數組，先存儲左側乘積，再動態計算右側乘積并直接合并。
2. 關鍵步驟
- 左側乘積計算：從左到右遍歷，將每個位置的左側乘積存入
answer數組。 - 右側乘積計算與合并：從右到左遍歷，用變量
right動態累積右側乘積，并同步更新answer數組。
3. 復雜度
? 時間復雜度：O(n)，兩次獨立的線性遍歷。
? 空間復雜度：O(1)（不考慮輸出數組的空間），僅使用常數額外空間。
三、圖解
四、邊界條件與擴展
1. 邊界條件
? 全零數組：如 nums = [0,0,0] → 結果為 [0,0,0]。
? 單個零元素：如 nums = [0,1,2] → 結果為 [2, 0, 0]。
? 數組長度為1：如 nums = [5] → 結果為 [1]（無其他元素可乘）。
2. 擴展驗證
? 負數情況：如 nums = [-1, 2, -3] → 結果為 [-6, 3, -2]。
? 大數溢出：題目保證結果在 32 位整數范圍內，無需額外處理。
五、總結
? 核心邏輯：通過左右分解避免重復計算，兩次遍歷實現高效求解。
? 優化關鍵：復用輸出數組存儲中間結果，空間復雜度從 O(n) 優化至 O(1)。
? 適用場景：類似“利用前后綴信息”的問題（如統計前后綴最大值、求和等）。
