238. Product of Array Except Self

題目理解

題目要求我們給定一個整數陣列 nums，返回一個新的陣列 answer，其中 answer[i] 等於 nums 陣列中除了 nums[i] 以外所有元素的乘積。要求我們在 O(n) 的時間複雜度內完成，而且不能使用除法

限制條件

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
保證答案在 32 位整數範圍內。

解題思路

Solution 1: Brute Force

暴力法的直覺是對於每個元素 nums[i]，計算陣列中除了 nums[i] 以外的所有元素的乘積。這需要兩層循環

這種方法的時間複雜度是 O(n^2)，因為對於每個元素，我們需要遍歷整個陣列來計算乘積

Solution 2: Prefix Sum

我們可以使用兩個輔助陣列來分別存儲每個位置的前綴積和後綴積

初始化：創建兩個大小為 n 的陣列 left 和 right，分別存儲每個位置的前綴積和後綴積
計算前綴積：
- left[i] 存儲位置 i 之前所有元素的乘積。
- left[0] 設為 1（因為在位置 0 之前沒有元素）
- 遍歷 nums，計算前綴積並存儲在 left 中
計算後綴積：
- right[i] 存儲位置 i 之後所有元素的乘積。
- right[n-1] 設為 1（因為在位置 n-1 之後沒有元素）
- 反向遍歷 nums，計算後綴積並存儲在 right 中
計算結果：最終結果 answer[i] 等於 left[i] 乘以 right[i]

這種方法的時間複雜度是 O(n)，因為我們只需遍歷陣列三次。空間複雜度也是 O(n)，因為我們需要兩個輔助陣列來存儲前綴積和後綴積

Solution 3: Prefix Sum (Optimized)

將前綴積和後綴積的概念合併到一個陣列中，並在一次遍歷中完成，從而實現 O(n) 的時間複雜度和 O(1) 的空間複雜度（不計輸出陣列）

初始化：創建一個大小為 n 的陣列 ans，初始值設為 1
計算前綴積：
- 使用一個循環計算每個位置的前綴積。前綴積是指在某一位置之前所有元素的乘積。
- 對於每個位置 i，ans[i] 等於 ans[i - 1] * nums[i - 1]
計算後綴積並最終計算結果
- 使用另一個循環從陣列的尾部開始計算每個位置的後綴積。後綴積是指在某一位置之後所有元素的乘積。
- 在計算後綴積的同時，更新 ans[i] 為 ans[i] * 後綴積，然後更新後綴積為 後綴積 * nums[i]

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        const int n = nums.size();
        vector<int> ans(n, 1);
        for (int i = 1; i < n; i += 1) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }

        int suffix = 1;
        for (int i = n - 1; i >= 0; i -= 1) {
            ans[i] *= suffix;
            suffix *= nums[i];
        }
        return ans;
    }
};

class Solution {
    public int[] productExceptSelf(int[] nums) {
        final int n = nums.length;
        int[] ans = new int[n];
        ans[0] = 1;

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

        int suffix = 1;
        for (int i = n - 1; i >= 0; i -= 1) {
            ans[i] *= suffix;
            suffix *= nums[i];
        }
        return ans;
    }
}

題目理解​

限制條件​

解題思路​

Solution 1: Brute Force​

Solution 2: Prefix Sum​

Solution 3: Prefix Sum (Optimized)​