2574. Left and Right Sum Differences

題目 / Problem

中文： 給你一個 0-indexed（下標從 0 開始）的整數陣列 nums，大小為 n。

定義兩個陣列 leftSum 和 rightSum： - leftSum[i] 是 nums 中下標 i 左邊所有元素的總和。如果左邊沒有元素，則 leftSum[i] = 0。 - rightSum[i] 是 nums 中下標 i 右邊所有元素的總和。如果右邊沒有元素，則 rightSum[i] = 0。

回傳一個大小為 n 的陣列 answer，其中 answer[i] = |leftSum[i] - rightSum[i]|（兩者差的絕對值）。

English: You are given a 0-indexed integer array nums of size n.

Define two arrays: - leftSum[i] = sum of all elements to the left of index i. If there is none, it is 0. - rightSum[i] = sum of all elements to the right of index i. If there is none, it is 0.

Return an array answer where answer[i] = |leftSum[i] - rightSum[i]| (the absolute value of the difference).

Constraints / 限制： - 1 <= nums.length <= 1000 - 1 <= nums[i] <= 10^5

Example / 範例：

Input:  nums = [10,4,8,3]
Output: [15,1,11,22]
leftSum  = [0,10,14,22]
rightSum = [15,11,3,0]
answer   = [|0-15|, |10-11|, |14-3|, |22-0|] = [15,1,11,22]

名詞解釋 / Glossary

• 前綴和 / prefix sum：從陣列開頭累加到某個位置的總和。我們用一個變數 left 逐步累加，就能在掃描時隨時知道「左邊的總和」，不必每次重新加。 A running total of elements from the start; we keep it in one variable so we always know the sum of everything seen so far without re-adding.
• 絕對值 / absolute value：一個數去掉正負號後的大小，例如 |-5| = 5。C 用 abs()，這裡也可以手寫成「若為負就取相反數」。The magnitude of a number ignoring its sign; |-5| = 5.
• 總和 / total sum：整個陣列所有元素相加的結果。先算出它，就能用「總和 − 左邊 − 自己」快速得到右邊的總和。The sum of every element; once known, the right sum is just total − left − nums[i].
• 動態配置記憶體 / malloc：在 C 裡用 malloc 向系統要一塊指定大小的記憶體來存放回傳陣列，因為陣列大小在執行時才決定。In C, malloc requests a block of memory at run time to hold the returned array.
• 回傳大小指標 / returnSize pointer：LeetCode 的 C 函式要求你透過一個指標 *returnSize 告訴呼叫者回傳陣列有多長。A pointer through which the function reports the length of the array it returns.

思路

最直接的做法（暴力法）是：對每一個下標 i，都跑一個內層迴圈把左邊所有元素加起來得到 leftSum，再跑一個內層迴圈把右邊所有元素加起來得到 rightSum，最後取差的絕對值。這樣每個 i 都要掃描幾乎整個陣列，總共是 O(n²) 的時間。雖然在 n ≤ 1000 的限制下也能通過，但我們可以做得更聰明。關鍵觀察是：右邊的總和不必每次重算。先用一次迴圈算出整個陣列的總和 total。接著從左到右掃描，維護一個變數 left 代表「目前下標左邊的元素總和」。當我們站在下標 i 時，右邊的總和必然等於 total − left − nums[i]，因為整個陣列扣掉左邊、再扣掉自己，剩下的就是右邊。算完 answer[i] 後，再把 nums[i] 累加進 left，讓它對下一個位置仍然正確——這個「left 永遠等於當前下標左側之和」就是我們的不變量（invariant）。如此只需掃描兩次，時間降到 O(n)。

The brute-force idea is: for every index i, run one inner loop to add up everything on its left and another to add up everything on its right, then take the absolute difference. That re-scans almost the whole array for each i, giving O(n²) time. It passes under n ≤ 1000, but we can do better. The key insight is that the right sum never needs to be recomputed from scratch. First, one pass computes the total of the whole array. Then we sweep left to right keeping a running variable left that holds the sum of everything strictly before the current index. At index i, the right sum must equal total − left − nums[i], since the whole array minus the left part minus the element itself is exactly the right part. After recording answer[i], we add nums[i] into left so the invariant — left always equals the sum of elements before the current index — holds for the next step. This needs only two passes, bringing the time down to O(n).

逐步走查 / Walkthrough

以 nums = [10, 4, 8, 3] 為例。先算總和 total = 10 + 4 + 8 + 3 = 25，並初始化 left = 0。

Using nums = [10, 4, 8, 3]: first total = 25, and start with left = 0.

最終 answer = [15, 1, 11, 22]，與題目期望輸出一致。 Final answer = [15, 1, 11, 22], matching the expected output.

Solution — C

// 演算法 / Algorithm:
// 先算出整個陣列的總和 total；再從左到右掃描，用 left 累積「左邊的和」，
// 右邊的和即為 total - left - nums[i]。每步取兩者差的絕對值。時間 O(n)。
// Compute the total once; sweep left-to-right keeping a running left sum,
// derive the right sum as total - left - nums[i], record the abs difference.

#include <stdlib.h>   // 提供 malloc / abs / Provides malloc and abs

// LeetCode 規定的函式簽名：回傳 int* 陣列，並透過 *returnSize 回報長度
// LeetCode's required signature: return an int* array and report its length via *returnSize
int* leftRightDifference(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;                          // 回傳陣列長度與輸入相同 / output has the same length n

    // 向系統要一塊能放 numsSize 個 int 的記憶體當作結果陣列
    // Allocate memory for numsSize ints to hold the answer
    int* answer = (int*)malloc(sizeof(int) * numsSize);

    long total = 0;                                  // 用 long 避免極端情況溢位 / long avoids any overflow risk
    for (int i = 0; i < numsSize; i++) {             // 第一次掃描：累加全部元素 / first pass: sum all elements
        total += nums[i];                            // total 變成整個陣列的和 / total becomes the whole-array sum
    }

    long left = 0;                                   // left = 目前下標「左邊」的元素和，初始為 0 / sum of elements before index i
    for (int i = 0; i < numsSize; i++) {             // 第二次掃描：逐位計算答案 / second pass: compute each answer
        long right = total - left - nums[i];         // 右邊和 = 全部 - 左邊 - 自己 / right sum = total minus left minus self
        long diff = left - right;                    // 左右差（可能為負）/ difference, may be negative
        if (diff < 0) diff = -diff;                  // 取絕對值：負數就變相反數 / take absolute value
        answer[i] = (int)diff;                       // 寫入結果，轉回 int / store result, cast back to int
        left += nums[i];                             // 把目前元素併入 left，供下一格使用 / extend left for the next index
    }

    return answer;                                   // 回傳結果陣列；呼叫者負責釋放 / caller frees this memory
}

Solution — C++

// 演算法 / Algorithm:
// 先求整個陣列的總和 total；再線性掃描，用 left 維護「左邊的和」，
// 右邊的和 = total - left - nums[i]，每步存入兩者差的絕對值。時間 O(n)。
// Compute total once, then sweep with a running left sum; right = total - left - nums[i].

#include <vector>     // 提供 std::vector 動態陣列 / provides the std::vector dynamic array
#include <numeric>    // 提供 std::accumulate 求和 / provides std::accumulate for summing
#include <cstdlib>    // 提供 std::abs / provides std::abs

class Solution {
public:
    std::vector<int> leftRightDifference(std::vector<int>& nums) {
        int n = nums.size();                         // n 是陣列大小 / n is the array length
        std::vector<int> answer(n);                  // 預先配置長度 n 的結果向量 / preallocate the answer vector

        // accumulate 把 nums 全部加起來；起始值寫 0L 讓累加用 long，避免溢位
        // accumulate sums the whole vector; the 0L seed accumulates in long to avoid overflow
        long total = std::accumulate(nums.begin(), nums.end(), 0L);

        long left = 0;                               // left = 當前下標左側元素之和 / sum of elements before index i
        for (int i = 0; i < n; i++) {                // 線性掃描每個下標 / linear sweep over indices
            long right = total - left - nums[i];     // 右側和由總和推得 / right sum derived from total
            answer[i] = std::abs(left - right);      // 存入左右差的絕對值 / store the absolute difference
            left += nums[i];                         // 更新 left 以維持不變量 / update left to keep the invariant
        }

        return answer;                               // 回傳向量，無需手動釋放 / return by value, no manual free
    }
};

複雜度 / Complexity

• Time: O(n) — 我們只掃描陣列兩次：一次求總和，一次計算每個答案；每次都是線性的，常數倍不影響量級。n 指陣列長度。 We make two linear passes over the array (one to total, one to compute answers); both are O(n) and n is the array length.
• Space: O(1) 額外空間（不計回傳陣列）—— 只用了 total、left、right 幾個變數。回傳陣列本身是題目要求的輸出，通常不計入額外空間。 Only a few scalar variables are used; the returned array is required output and not counted as extra space.

Pitfalls & Edge Cases

• 單一元素 / single element：當 n == 1 時，左右都沒有元素，left = 0 且 right = total - 0 - nums[0] = 0，答案為 0。我們的公式自然處理這種情況，不需特判。 With one element both sides are empty; the formula yields 0 automatically.
• 溢位 / overflow：最壞情況下總和約為 1000 × 10^5 = 10^8，仍在 32 位元 int（約 2.1×10^9）範圍內，所以本題其實不會溢位。但我們仍用 long 累加作為安全習慣——當約束更大時這能避免難找的錯誤。 Here the max total is ~10^8, within int range, but using long is a safe habit for larger constraints.
• 不要每格重算右和 / don't recompute the right sum each step：用內層迴圈重算會退化成 O(n²)。正確做法是利用 total - left - nums[i] 在 O(1) 時間得到右和。 Re-summing the right side per index is O(n²); deriving it from total keeps each step O(1).
• 記住更新 left / remember to update left：迴圈尾端的 left += nums[i] 不能漏，否則不變量被破壞，後續所有答案都會錯。 Forgetting left += nums[i] breaks the invariant and corrupts every later answer.
• C 的 returnSize / returnSize in C：忘記設定 *returnSize 會讓 LeetCode 讀到錯誤長度，導致結果被截斷或越界。 Failing to set *returnSize makes the grader read a wrong length.