原文題目

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

題目摘要

1. 題目描述：給定一個整數陣列 nums，回傳一個陣列 answer，其中 answer[i] 等於 nums 中除了 nums[i] 以外的所有元素的乘積。
2. 輸入：一個整數陣列 nums。
3. 輸出：一個整數陣列 answer。
4. 限制條件：不允許使用除法。

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

解題思路

1. 解題關鍵：
   • 透過兩次遍歷，分別計算出每個位置左側與右側的乘積，然後將這兩者結合起來。
2. 左側乘積：
   • 我們先遍歷陣列，並計算出每個位置上「其左側」所有數的乘積，這個乘積保存在結果陣列中。
3. 右側乘積：
   • 接著我們從右向左遍歷陣列，並在結果陣列中乘上「其右側」的所有數的乘積，這樣就能得到最終結果。

程式碼

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];  //建立結果陣列 res，並定義其大小為n
        res[0] = 1; //設定res的第一個元素為1，因為它左邊沒有元素

        //第一個循環：計算每個元素的左側乘積
        //res[i]將會儲存nums[i]左側所有元素的乘積
        for (int i = 1; i < n; i++) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        int right = 1; //宣告變數right來追蹤右側所有元素的乘積
        
        //第二個循環：計算每個元素的右側乘積，並與左側乘積相乘
        //從右至左遍歷，將右側的乘積更新到res陣列中
        for (int i = n - 1; i >= 0; i--) {
            res[i] *= right; //將res[i]乘上右側所有元素的乘積
            right *= nums[i]; //更新右側的乘積
        }
        return res; //回傳最終結果
    }
}

結論： 這道題可以讓我們思考如何在有限的時間內有效處理大量資料。現實生活中，像是工作專案，當你需要在不干擾單一數據的情況下，分析一個系統內其他所有環節的影響，這種「左右平衡」的思維方式很有用。解題的巧妙之處在於，通過兩次遍歷分別計算左邊和右邊的乘積，避免了直接除法或多餘的空間浪費。這就像你先從一方面看問題，再從另一面補充，最後融合成完整的解答，既節省時間，又避免冗餘。