主題: 學習筆記
LeetCode 724：TypeScript 尋找陣列 Pivot Index
用總和與左側累積值在線性時間找出最左 pivot index，並釐清雙迴圈、額外空間與迴圈不變量。
這篇筆記從原始實作出發，使用 AI 協助檢查推導與驗證案例。發布前重新核對了程式行為、複雜度與題目限制。
題目
對應原題：LeetCode 724：Find Pivot Index
給定整數陣列 nums，找出最左邊的索引 i，使 i 左側元素總和等於右側元素總和。陣列邊界外的一側總和為 0。沒有符合的索引時回傳 -1。
例如 [1, 7, 3, 6, 5, 6] 的答案是 3，因為左側總和 1 + 7 + 3 和右側總和 5 + 6 都是 11。
原始寫法沒有算錯，但說明少了幾個面試重點
原始實作先加總整個陣列，再從左到右維護左側總和。
function pivotIndex(nums: number[]): number {
let total = 0;
for (let index = 0; index < nums.length; index += 1) {
total += nums[index];
}
let leftSum = 0;
for (let index = 0; index < nums.length; index += 1) {
const rightSum = total - leftSum - nums[index];
if (leftSum === rightSum) return index;
leftSum += nums[index];
}
return -1;
}這段程式會回傳正確答案，也不會改動輸入。需要補強的是解釋，而不是重寫成更複雜的資料結構。
- 兩次完整掃描是
O(2n)，Big O 會省略常數，因此應寫成O(n)。 total、leftSum與每輪的rightSum都是固定數量的數值，額外空間是O(1)，不是O(n)。- 只寫出公式還不夠。面試時要交代
leftSum在判斷前代表哪一段資料，以及為何從左到右回傳就得到最左答案。 console.log()不能驗證結果，需要 assertion 讓錯誤直接失敗。
若每個索引都重新計算左側和與右側和，會重複掃描同一批元素，時間會變成 O(n²)。
較佳方案：保留同一個想法，說清楚狀態
原始方法已經是適合面試的方案。以下版本只調整命名與說明焦點。
function pivotIndex(nums: number[]): number {
const total = nums.reduce((sum, num) => sum + num, 0);
let leftSum = 0;
for (let index = 0; index < nums.length; index += 1) {
const rightSum = total - leftSum - nums[index];
if (leftSum === rightSum) return index;
leftSum += nums[index];
}
return -1;
}total 包含所有元素。處理索引 index 時，leftSum 還不包含 nums[index]，所以從 total 扣掉兩者後，留下的正好是 index 右側的總和。
為什麼正確
每次迴圈開始前，leftSum 等於 nums[0] 到 nums[index - 1] 的總和。
第一輪時 index 是 0，左側沒有元素，leftSum 的初始值 0 正確。假設某一輪開始時這個條件成立，total - leftSum - nums[index] 就會是 nums[index + 1] 到最後一個元素的總和。若兩側相等，當前索引符合題意；否則把 nums[index] 加進 leftSum，下一輪的條件仍成立。
迴圈由左往右檢查，遇到第一個符合的索引就回傳，因此結果一定是最左的 pivot index。
最小驗證
import assert from "node:assert/strict";
assert.equal(pivotIndex([1, 7, 3, 6, 5, 6]), 3);
assert.equal(pivotIndex([1, 2, 3]), -1);
assert.equal(pivotIndex([5]), 0);
assert.equal(pivotIndex([0, 0]), 0);單一元素和連續零值可檢查邊界外總和視為 0，也可確認函式回傳最左答案。
複雜度與可遷移觀念
第一次掃描計算總和，第二次掃描找 pivot，因此總時間是 O(n)。除了幾個數值變數外沒有建立工作陣列，額外空間是 O(1)。
這個模式常出現在「左邊已處理的資料」和「右邊尚未處理的資料」之間。先取得整體總和，再維護前綴狀態，就能在不建立 prefix sum 陣列的情況下取得右側總和。
常見陷阱
- 把目前元素算進左側或右側其中一邊。
- 找到符合的索引後仍繼續掃描，最後回傳較右邊的答案。
- 把兩次掃描寫成
O(2n)，卻沒有化簡成O(n)。 - 把固定數量變數誤判成
O(n)額外空間。
外部參考連結
- LeetCode 724：Find Pivot Index：原始題目、範例與限制。
- TypeScript Handbook：More on Functions：函式參數與回傳型別語法。
- Node.js：assert.equal()：以 assertion 驗證程式結果。