一、问题描述

给定一个整数数组 nums，请找到一个下标，使得该下标左侧所有元素相加的和等于右侧所有元素相加的和。如果不存在这样的下标，返回 -1。数组中可能存在多个中心下标，你应该返回最靠近左边的那一个。

二、方案一：暴力法

1、思路

遍历数组中的每个下标，对于每个下标，计算其左右两侧元素的和，判断是否相等。

2、代码实现

func findCenterIndex(nums []int) int {
    for i := range nums {
        if sum(nums[:i]) == sum(nums[i+1:]) {
            return i
        }
    }
    return -1
}
func sum(nums []int) int {
    total := 0
    for _, num := range nums {
        total += num
    }
    return total
}

3、复杂度分析

• 时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。我们需要遍历每个下标，并计算左右两侧的和。
• 空间复杂度：O(1)，只使用了常数空间。

三、方案二：前缀和

1、思路

首先计算整个数组的总和 total，然后再次遍历数组，使用一个变量 leftSum 来记录当前下标左侧元素的和。对于每个下标，我们可以通过 total - leftSum - nums[i] 来计算右侧元素的和，并与 leftSum 比较。

2、代码实现

func findCenterIndex(nums []int) int {
    total := sum(nums)
    leftSum := 0
    for i, num := range nums {
        if leftSum == total - leftSum - num {
            return i
        }
        leftSum += num
    }
    return -1
}
func sum(nums []int) int {
    total := 0
    for _, num := range nums {
        total += num
    }
    return total
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需要遍历数组两次。
• 空间复杂度：O(1)，只使用了常数空间。

四、总结

方案	时间复杂度	空间复杂度	备注
方案一	O(n^2)	O(1)	暴力法
方案二	O(n)	O(1)	使用前缀和优化

方案二在时间和空间复杂度上都优于方案一，因此推荐使用方案二。