724. Find Pivot Index

📘 題目敘述

給定一個整數陣列 nums，請找出樞紐索引（pivot index）。

樞紐索引的定義是：該索引左邊所有元素的總和，等於右邊所有元素的總和。

如果樞紐索引存在，請回傳最左邊的那一個。

如果不存在，回傳 -1。

條件限制

1 <= nums.length <= 10^4
-1000 <= nums[i] <= 1000

🧠 解題思路

我的想法是用兩個累加值去維護「左邊總和」與「右邊總和」：

l：目前 pos 左邊所有元素的總和
r：目前 pos 右邊所有元素的總和

我先把 r 初始化成「除了 nums[0] 以外的總和」，

這樣一開始 pos = 0 時：

左邊沒有元素 → l = 0
右邊是 nums[1..] → r 已經算好

接著我用 while 迴圈讓 pos 從左到右掃過去：

每一輪先檢查 l == r，如果成立就是 pivot
否則就把 nums[pos] 加進左邊、pos++
再把新的 nums[pos] 從右邊扣掉（因為它不再在右邊了）

這樣可以用 O(n) 的時間一路更新，不用每次都重新加總。

所有變數

nums：題目給的陣列（我在程式中有額外 push_back(0)）
l：目前索引 pos 左側的總和
r：目前索引 pos 右側的總和
pos：目前正在檢查的索引位置
i：用來先計算 r 的迴圈索引

🪜 主要流程步驟

第一步：處理超小陣列

如果 nums.size() < 2，我直接回傳 0
- 因為只有一個元素時，左邊和右邊都是空集合，加總都是 0
- 所以 pivot 就是 0

第二步：先算出初始右邊總和 `r`

for (int i = 1; i < nums.size(); i++) {
    r += nums[i];
}

這樣設定後：

pos = 0
l = 0（左邊沒有）
r = nums[1] + nums[2] + ...（右邊全部）

第三步：補一個 `0` 防止越界（我這份寫法的關鍵小技巧）

nums.push_back(0);

因為我後面會做 pos++ 然後立刻使用 nums[pos] 來更新 r：

pos++;
r -= nums[pos];

如果 pos 走到最後一個元素的位置，再 pos++ 就會越界。

所以我在尾巴補一個 0，讓最後一次更新時仍然安全。

第四步：從左到右掃描找 pivot

while 迴圈每輪做的事情：

檢查是否為 pivot
- 若 l == r → 直接回傳 pos
更新左邊總和
- l += nums[pos]
- 表示把目前這格納入左邊
索引往右移
- pos++
更新右邊總和
- r -= nums[pos]
- 因為新的 pos 位置不再算在右邊（它現在是「中心」）

第五步：找不到就回傳 -1

如果掃完整個陣列都沒有 l == r，就回傳 -1。

💻 程式碼實作

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        if (nums.size() < 2) {
            return 0;
        }
        int l = 0, r = 0;
        int pos = 0;
        for (int i = 1; i < nums.size(); i++) {
            r += nums[i];
        }
        nums.push_back(0);
        while (pos < nums.size() - 1) {
            if (l == r) {
                return pos;
            }
            l += nums[pos];
            pos++;
            r -= nums[pos];
        }
        return -1;
    }
};

🔗 題目連結

https://leetcode.com/problems/find-pivot-index/