04/80 寻找数组的中心下标

题目描述

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组的左端，那么左侧数之和视为 0 ，因为下标的左侧不存在元素。这一点对于中心下标位于数组右端的情况同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那个。如果数组不存在中心下标，返回 -1 。

---

核心思路：前缀和思想

这道题最直白的解法是对每个位置都重新计算左右两侧之和，但那样复杂度会达到 $O(N^2)$。利用“前缀和”的思想，我们可以将复杂度优化到 $O(N)$。

1. 数学推导

设数组总和为 totalSum，当前下标为 i，其左侧元素之和为 leftSum，当前元素值为 nums[i]。
根据题目要求，如果 i 是中心下标，则其右侧之和也必须等于 leftSum。

那么整个数组的和可以表示为：
$$totalSum = leftSum + nums[i] + rightSum$$

因为 $rightSum = leftSum$，所以：
$$totalSum = leftSum + nums[i] + leftSum$$
$$totalSum = 2 \times leftSum + nums[i]$$

结论：我们只需维护一个变量 leftSum，在遍历过程中检查 2 * leftSum + nums[i] == totalSum 是否成立即可。

---

代码实现 (Kotlin)

class Solution {
    /**
     * 寻找数组的中心下标
     * @param nums 整数数组
     * @return 中心下标，若不存在则返回 -1
     */
    fun pivotIndex(nums: IntArray): Int {
        // 1. 先计算数组的总和
        val totalSum = nums.sum()
        
        // 2. 维护左侧元素之和
        var leftSum = 0
        
        // 3. 遍历数组寻找满足条件的下标
        for (i in nums.indices) {
            val currentValue = nums[i]
            
            // 检查：2 * 左侧和 + 当前值 == 总和
            // 这等价于：左侧和 == 总和 - 左侧和 - 当前值（即右侧和）
            if (2 * leftSum + currentValue == totalSum) {
                return i
            }
            
            // 更新左侧和，供下一个位置使用
            leftSum += currentValue
        }
        
        return -1
    }
}

fun main() {
    val solution = Solution()
    val nums = intArrayOf(1, 7, 3, 6, 5, 6)
    // 预期输出：3
    // 解释：左侧和 (1+7+3=11)，右侧和 (5+6=11)
    println("中心下标为: ${solution.pivotIndex(nums)}")
}

---

复杂度分析

• 时间复杂度：$O(N)$。其中 $N$ 是数组的长度。我们首先进行了一次 $O(N)$ 的求和，然后又进行了一次 $O(N)$ 的遍历。
• 空间复杂度：$O(1)$。我们只使用了常数级别的额外空间（totalSum 和 leftSum 变量）。

---

关键点总结

1. 空间优化：不需要像传统的“前缀和”问题那样创建一个 $O(N)$ 长度的辅助数组，仅通过两个变量动态维护状态即可。
2. 边界处理：
   • 当 i = 0 时，leftSum 初始为 0。如果 0 + nums[0] + 0 == totalSum，说明第一个元素就是中心下标，逻辑完美兼容。
3. 最左侧优先：通过 for 循环从前向后遍历，一旦找到第一个满足条件的下标就立即返回，确保了结果是“最靠近左边”的。