Find Pivot Index
題目描述
給定整數陣列 nums，找出「樞紐索引」— 使得左邊元素之和等於右邊元素之和的索引。不存在時回傳 -1。
輸入：nums = [1,7,3,6,5,6]
輸出：3（左邊 1+7+3=11，右邊 5+6=11）
輸入：nums = [1,2,3]
輸出：-1
輸入：nums = [2,1,-1]
輸出：0（左邊為空=0，右邊 1+(-1)=0）
解題思路
算總和
先遍歷一次陣列，計算 totalSum = sum(nums)，例如 [1,7,3,6,5,6] → 28
初始化左和
leftSum = 0，代表索引 0 左邊沒有元素
遍歷每個索引
對每個 i，算 rightSum = totalSum - leftSum - nums[i]（總和減去左邊和支點本身）
判斷
若 leftSum == rightSum，找到 pivot，回傳 i
累加
leftSum += nums[i]，把當前元素加入左邊，繼續檢查下一個索引
程式碼
C#
public class Solution {
public int PivotIndex(int[] nums) {
int totalSum = nums.Sum();
int leftSum = 0;
for (int i = 0; i < nums.Length; i++) {
int rightSum = totalSum - leftSum - nums[i];
if (leftSum == rightSum) return i;
leftSum += nums[i];
}
return -1;
}
}TypeScript
function pivotIndex(nums: number[]): number {
const totalSum = nums.reduce((a, b) => a + b, 0);
let leftSum = 0;
for (let i = 0; i < nums.length; i++) {
const rightSum = totalSum - leftSum - nums[i];
if (leftSum === rightSum) return i;
leftSum += nums[i];
}
return -1;
}Python
def pivotIndex(nums: list[int]) -> int:
total_sum = sum(nums)
left_sum = 0
for i, num in enumerate(nums):
right_sum = total_sum - left_sum - num
if left_sum == right_sum:
return i
left_sum += num
return -1複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |
先算總和遍歷一次 O(n)，再從左到右掃描一次 O(n)，每步做常數次加法和比較。兩次遍歷合計 O(n)。只用 totalSum、leftSum 兩個變數，空間 O(1)。
邊界情況
- pivot 在索引 0：例如
[2,1,-1]，leftSum = 0，rightSum = 1 + (-1) = 0，回傳 0 - pivot 在最後一個索引：例如
[-1,1,2]，leftSum = -1+1 = 0，rightSum = 0，回傳 2 - 不存在 pivot：例如
[1,2,3]，任何位置左右和都不相等，回傳 -1
圖解
圖表展示找到 pivot 的關鍵步驟：陣列總和為 28，在 i=3 時 leftSum = 1+7+3 = 11，rightSum = 28 - 11 - 6 = 11，左右相等，索引 3 即為 pivot。
進階觀點
💡面試追問
-
Q: 索引 0 可以是 pivot 嗎？ A: 可以。左邊為空，和定義為 0。如果 rightSum = totalSum - nums[0] 也等於 0，索引 0 就是 pivot。例如
[0,0,0]的 pivot 是 0。 -
Q: 有多個 pivot 怎麼辦？ A: 題目要求回傳最左邊的那個，所以從左往右掃描找到第一個就回傳。如果要找所有 pivot，改為收集到 list 即可。
-
Q: 含有負數時演算法還正確嗎？ A: 正確。演算法用的是精確的整數加法比較，不涉及排序或大小假設。負數會使 leftSum 可能先增後減，但公式
rightSum = totalSum - leftSum - nums[i]始終成立。 -
Q: 跟前綴和陣列的關係？ A: 這題本質上就是找前綴和陣列中
prefix[i] == totalSum - prefix[i+1]的位置。但不需要額外建立前綴和陣列，用一個 leftSum 變數逐步累加即可。
理解測驗
🤔 為什麼 rightSum = totalSum - leftSum - nums[i]？
🤔 nums = [0,0,0] 的 pivot index 是什麼？