給定整數陣列
nums，找到 pivot index，使得左邊所有元素之和等於右邊所有元素之和。如果不存在回傳 -1。如果有多個，回傳最左邊的。
Example:
Input: nums = [1,7,3,6,5,6] Output: 3
Intuition
TIP
核心思路：先算總和，然後遍歷時維護左側和 leftSum，右側和即為 totalSum - leftSum - nums[i]。
- 不需要真的算兩次前綴和，只要知道總和，就能用
totalSum - leftSum - nums[i]得到右側和 - 當
leftSum == totalSum - leftSum - nums[i]時，找到了 pivot
Approaches
1. Brute-Force Prefix Sum — O(n^2) / O(1)
- Idea: 對每個位置分別計算左側和與右側和
- Time:
O(n^2)- 每個位置都要計算子陣列和 - Space:
O(1)
class Solution {
fun pivotIndex(nums: IntArray): Int {
for (i in nums.indices) {
var leftSum = 0
for (j in 0 until i) leftSum += nums[j]
var rightSum = 0
for (j in i + 1 until nums.size) rightSum += nums[j]
if (leftSum == rightSum) return i
}
return -1
}
}⭐ 2. Single Pass (total − left sum) — O(n) / O(1)
- Idea: 先計算總和，遍歷時維護左側累積和，右側和 = 總和 - 左側和 - 當前值
- Time:
O(n)- 兩次遍歷（一次求和、一次掃描） - Space:
O(1)- 只用常數變數
class Solution {
fun pivotIndex(nums: IntArray): Int {
val totalSum = nums.sum()
var leftSum = 0
for (i in nums.indices) {
if (leftSum == totalSum - leftSum - nums[i]) {
return i
}
leftSum += nums[i]
}
return -1
}
}🔑 Takeaways
- Pattern: Prefix Sum 的變體——利用總和避免重複計算
- Key trick:
rightSum = totalSum - leftSum - nums[i]是核心公式；注意 pivot 本身不計入任何一邊