寻找数组的中心索引

Posted on Edited on In Word count in article: 846 Reading time ≈ 1 mins.
寻找数组的中心索引，求和

给你一个整数数组 nums，请编写一个能够返回数组 “中心索引” 的方法。

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

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

注意：中心索引可能出现在数组的两端。

1
2
input = [1, 7, 3, 6, 5, 6]
res = 3

直接遍历解法，两边求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func pivotIndex(nums []int) int {
    for i:=0;i<len(nums);i++ {
        leftRes, rightRes := 0, 0
        if i > 0{
            for _, j := range nums[:i] {
                leftRes += j
            }
        }
        if i < len(nums) - 1 {
            for _, k := range nums[i:] {
                rightRes += k
            }
            rightRes -= nums[i]
        }
        if leftRes == rightRes {
            return i
        }
    }
    return -1
}

优化：总和是不变的，先求一遍总和，然后只求一边的和，得到另一边的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func pivotIndex(nums []int) int {
    sum := 0
    // 先算总和
    for i:=0;i<len(nums);i++ {
        sum += nums[i]
    }

    leftRes := 0
    // 循环遍历求左边的和
    for i:=0;i<len(nums);i++ {
    	// 不计算当前值
        if  i > 0 {
            leftRes += nums[i-1]
        }
        // 计算右边的和时候减去当前值
        if leftRes == sum - leftRes - nums[i] {
            return i
        }
    }
    return -1
}