/*
 * Same two-pass algorithm, idiomatic C++ with std::vector.
 * 相同的兩次掃描演算法，使用 std::vector 寫成符合 C++ 慣例的版本。
 * Pass 1: answer[i] = product of nums to the LEFT of i.
 * Pass 2: multiply in the product of nums to the RIGHT of i using a single scalar.
 * 時間 O(n)、額外空間 O(1)（不計輸出向量）。
 */
class Solution {
public:
    /* vector<int> is a dynamically-sized array container; passed by const reference for efficiency. */
    /* vector<int> 是可動態調整大小的陣列容器；用 const 參考傳入避免複製。 */
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();              /* n = number of elements / 元素個數 */

        /* Construct the output vector of length n, every slot pre-initialized to 1. */
        /* 建立長度為 n 的輸出向量，每格初始化為 1（乘法單位元）。 */
        vector<int> answer(n, 1);

        /* Pass 1: left-to-right sweep building prefix products into answer. */
        /* 第一次掃描：由左至右建立前綴乘積。 */
        int left = 1;                     /* running product of nums[0..i-1] / i 左邊累積乘積 */
        for (int i = 0; i < n; ++i) {
            answer[i] = left;             /* write the current left product BEFORE folding in nums[i] / 先寫入再更新 */
            left *= nums[i];              /* update the running left product / 更新左側累積乘積 */
        }

        /* Pass 2: right-to-left sweep multiplying in suffix products. */
        /* 第二次掃描：由右至左乘上後綴乘積。 */
        int right = 1;                    /* running product of nums[i+1..n-1] / i 右邊累積乘積 */
        for (int i = n - 1; i >= 0; --i) {
            answer[i] *= right;           /* combine left (already stored) and right products / 結合左右兩側乘積 */
            right *= nums[i];             /* update the running right product / 更新右側累積乘積 */
        }

        /* Return by value; modern C++ moves the vector out cheaply (no full copy). */
        /* 以值回傳；現代 C++ 會以 move 高效轉移，不會整份複製。 */
        return answer;
    }
};