題目網址：https://leetcode.cn/problems/product-of-array-except-self/

題意：給一 array nums, 返回一 array answer, 其中 answer[i] 為 nums 中除了 nums[i] 以外其餘元素的乘積, 乘積保證在 32-bit 整數的範圍內（不用考慮 overflow）。

注意：請不要使用除法, 並在 $O(n)$ time 內解決此問題

進階：請設計 $O(1)$ space 的演算法, 其中 output array 不算額外空間

Solution 1：

想法：利用 prefix 和 postfix, 以 index = i 為分界, prefix[i] 記錄區間 [0, i - 1] 之乘積, postfix[i] 記錄區間 [i + 1, n - 1] 之乘積, 最後 nums[i] = prefix[i] * postfix[i] 即為題目所求

  • prefix：prefix[i] 紀錄 num[0] ~ nums[i - 1] 的乘積（由前往後填）
  • postfix：postfix[n - i - 1] 紀錄 nums[n - 1] ~ nums[n - i] 的乘積（由後往前填）
  • nums：nums[i] 紀錄 prefix[i] * postfix[i], 也就是除了位置 i 剩餘其他數的乘積

e.g. nums = [1,2,3,4]

nums 1 2 3 4
prefix 1 1 2 6
postfix 24 12 4 1
nums 24 12 8 6 
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix(n, 1), postfix(n, 1);

        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] * nums[i - 1];
            postfix[n - i - 1] = nums[n - i] * postfix[n - i];
        }

        for (int i = 0; i < n; i++) {
            nums[i] = prefix[i] * postfix[i];
        }
        return nums;
    }
};
  • time：$O(n)$ ➔ 遍歷 nums
  • space：$O(n)$ ➔ prefix, postfix

Solution 2：

想法：改進 Solution 1, 將 prefix 直接儲存在 res 中, 然後計算出 postfix 後乘上對應的 prefix

nums:   [ 1,  2, 3, 4]
➔ res: [24, 12, 4, 1] // postfix 做完
➔ res: [24, 12, 8, 6] // prefix 做完
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        const int n = nums.size();
        vector<int> res(n, 1);

        // 計算 postfix
        for (int i = 1; i < n; i++) {
            res[n - i - 1] = res[n - i] * nums[n - i];
        }

        int prefix = nums[0];
        for (int i = 1; i < n; i++) {
            res[i] *= prefix;
            prefix *= nums[i];
        }
        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷 nums
  • space：$O(1)$ ➔ 撇除要返回的 output array res, 只需常數空間