今天的題目是: 238. Product of Array Except Self

題目大意是: (Problem Description)給定一個整數數組 nums，返回一個新數組，其中 answer[i] 等於 nums 中除 nums[i] 以外所有元素的乘積。
約束條件：請勿使用除法運算。時間複雜度必須是 $O(n)$。

class Solution {
    /**
     * 計算除自身以外數組的乘積 (Product of Array Except Self)
     * 遵循 O(n) 時間複雜度且不使用除法。
     * * @param nums 輸入的整數數組
     * @return 輸出數組 answer，其中 answer[i] 是 nums 中除 nums[i] 外所有元素的乘積
     */
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        
        // 初始化結果數組 answer。它也將被用作第一個遍歷中的「左側乘積數組」。
        int[] answer = new int[n];
        
        // === 第一次遍歷：計算左側乘積 (L) ===
        
        // leftProductAccumulator 累積 nums[i] 左邊所有元素的乘積
        int leftProductAccumulator = 1;
        
        for (int i = 0; i < n; i++) {
            // 1. answer[i] 暫存的是所有在 nums[i] 左邊元素的乘積 (L[i])
            //    對於 i=0，左側沒有元素，乘積為 1。
            answer[i] = leftProductAccumulator;
            
            // 2. 將當前元素乘進累積器，準備用於計算 i+1 位置的左側乘積
            leftProductAccumulator *= nums[i];
        }
        
        // 經過第一次遍歷後，answer 數組儲存了所有位置的左側乘積。
        // 例如：nums=[1, 2, 3, 4] -> answer=[1, 1, 2, 6]
        
        
        // === 第二次遍歷：計算右側乘積 (R) 並與左側乘積相乘 ===
        
        // rightProductAccumulator 累積 nums[i] 右邊所有元素的乘積
        int rightProductAccumulator = 1;
        
        // 從右邊開始向左遍歷
        for (int i = n - 1; i >= 0; i--) {
            // 1. answer[i] (左側乘積 L[i]) 乘以 rightProductAccumulator (右側乘積 R[i]) 
            //    得到最終結果 answer[i] = L[i] * R[i]
            answer[i] *= rightProductAccumulator;
            
            // 2. 將當前元素乘進累積器，準備用於計算 i-1 位置的右側乘積
            rightProductAccumulator *= nums[i];
        }
        
        return answer;
    }
}