724. Find Pivot Index

Easy

Description

給定整數陣列 nums，找到 pivot index，使得左邊所有元素之和等於右邊所有元素之和。如果不存在回傳 -1。如果有多個，回傳最左邊的。

Example:

Input: nums = [1,7,3,6,5,6] Output: 3

Intuition#

核心思路：先算總和，然後遍歷時維護左側和 leftSum，右側和即為 totalSum - leftSum - nums[i]。

不需要真的算兩次前綴和，只要知道總和，就能用 totalSum - leftSum - nums[i] 得到右側和
當 leftSum == totalSum - leftSum - nums[i] 時，找到了 pivot

Approaches#

1: 暴力前綴和#

概念: 對每個位置分別計算左側和與右側和
時間複雜度: O(n^2) - 每個位置都要計算子陣列和
空間複雜度: 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: 一次遍歷（總和 - 左側和）#

概念: 先計算總和，遍歷時維護左側累積和，右側和 = 總和 - 左側和 - 當前值
時間複雜度: O(n) - 兩次遍歷（一次求和、一次掃描）
空間複雜度: 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 的變體——利用總和避免重複計算
關鍵技巧: rightSum = totalSum - leftSum - nums[i] 是核心公式；注意 pivot 本身不計入任何一邊