LeetCode Product of Array Except Self：除自身以外數組的乘積 — 前後綴積 O(1) 空間

題目描述

給定長度 n>1 的整數數組 nums，返回數組 output，其中 output[i] 等於除 nums[i] 外所有元素的乘積。要求：不使用除法，時間 O(n)，空間 O(1)（不含輸出）。

範例： [1,2,3,4] → [24,12,8,6]

解題思路：前後綴積單次遍歷

用 left 累積左側乘積，right 累積右側乘積。一次循環同時從左向右、從右向左更新結果數組：

• res[i] *= left; left *= nums[i];
• res[n-1-i] *= right; right *= nums[n-1-i];

參考代碼 (C++)

class Solution {
public:
    vector productExceptSelf(vector& nums) {
        int n = nums.size();
        vector res(n, 1);
        int left = 1, right = 1;
        for (int i = 0; i < n; ++i) {
            res[i] *= left;
            left *= nums[i];
            res[n-1-i] *= right;
            right *= nums[n-1-i];
        }
        return res;
    }
};

複雜度分析

• 時間：O(n) —— 單次遍歷。
• 空間：O(1) 額外空間（輸出數組不計入）。