题干
给你一个整数数组 nums
,请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端,那么左侧数之和视为 0
,因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标,应该返回 最靠近左边 的那一个。如果数组不存在中心下标,返回 -1
。
示例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 解释: 数组中不存在满足此条件的中心下标。
示例3:
输入:nums = [2, 1, -1] 输出:0 解释: 中心下标是 0 。 左侧数之和 sum = 0 ,(下标 0 左侧不存在元素), 右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
提示:
1 <= nums.length <= 10^4
-1000 <= nums[i] <= 1000
解题思路
本题的意思就是,一个数组中有若干元素,是否存在一个数,它的左边元素的和与它的右边元素的和相等,若存在,输出这个数的下标;若不存在,输出-1。
如示例1所示,1+7+3=11,5+6=11,存在元素6,它的两边各自元素和相等。
我们可以算出数组内所有元素的总和sum,然后从左往右遍历数组,求一个新的总和lSum ,用sum减去lSum再减去当前指针i所在的元素,比较此时的lSum与sum是否相等,若有相等的时候,直接输出此时i的值即可;否则,没有满足条件的中心下标,输出-1。
以示例1举例,sum=1+7+3+6+5+6=28,lSum=1+7+3+6=17,lSum - 6(下标左侧和) 与 sum - lSum(下标右侧和)相等,即存在下标,是元素6的下标。
AC代码
class Solution {
public int pivotIndex(int[] nums) {
int lSum = 0, sum = 0;
for(int num : nums ){
sum = sum + num;
}
for(int i=0;i<nums.length;i++){
lSum = lSum + nums[i];
sum = sum - nums[i];
if(lSum - nums[i] == sum ){
return i;
}
}
return -1;
}
}