Leetcode 724. 寻找数组的中心下标

724. 寻找数组的中心下标

724. 寻找数组的中心下标

• 标签：数组、前缀和

• 难度：简单

描述：给定一个数组 nums。

要求：找到「左侧元素和」与「右侧元素和相等」的位置，若找不到，则返回 -1。

说明：

• 1 <= nums.length <= 104

• -1000 <= nums[i] <= 1000

示例：

• 示例 1：

输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11，二者相等。

• 示例 2：

输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。

思路

要找的中心下标存在明显的数量关系：中心下标的左边之和 + nums[中心下标] + 中心下标的右边之和 = 数组之和。所以采取2次遍历：

• 第1次遍历，计算整个数组之和sum。

• 第2次遍历，left=遍历位置的左边之和，right （遍历位置的右边之和）= sum - nums[遍历位置] - left。判断 left 和 right 是否相等，相等则找到了中心下标；否则，此位置不是中心下标，继续下一个位置比较。

public int pivotIndex(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
        }
        int left = 0;
        int right = 0;
        for (int i = 0; i < nums.length; i++) {
                if (i == 0){
                        right = sum - nums[i];
                }else{
                        left += nums[i - 1];
                        right = sum - nums[i] - left;
                }
                if (left == right){
                        return i;
                }
        }
        return -1;
}

第2次遍历还可以优化代码，中心下标条件是：中心下标的左边之和 + nums[中心下标] + 中心下标的右边之和 = 数组之和，即 2*中心下标的左边之和 + nums[中心下标] = sum。

public int pivotIndex(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
        }
        int left = 0;
        for (int i = 0; i < nums.length; i++) {
                if (2 * left + nums[i] == sum)
                        return i;
                left += nums[i];
        }
        return -1;
}