724.寻找数组的中心下标

发表于： 分类于：
字数： 840 阅读：≈ 2分钟

❤‍🔥 724.寻找数组的中心下标

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

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

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

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

思路

基本思想

找中心下标肯定是两端向中间逼近，这种题目适合用双指针法，从两头分别开始向中间移动。

最初的想法是从两端向中间移动，一旦有一端小了，这一端就需要累加，当两端一样大时，就同时累加，知道两个指针相遇，也就是：

  1. 左小于右，左向后累加
  2. 右小于左，右向前累加
  3. 两者相等，一起累加

但是这样只考虑了数组中元素为正的情况，一旦出现[-1,-1,-1,-1,-1,0]的情况，此时就会出现左边一直向后累加，直到走到数组末尾的情况，其实数组中的元素可以为负，错误代码为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        //从两端向中间移动，谁小移动谁，一旦相等就同时移动
        int i=0,j=nums.size()-1;
        int rsum=nums[nums.size()-1];
        int lsum=nums[0];
        while(i<j){
            if(rsum>lsum){//左边的小
                ++i;
                lsum+=nums[i];
            }
            else if(rsum<lsum){//右边的小
                --j;
                rsum+=nums[j];
            }
            else{//两个一样大 
                ++i;
                --j;
                lsum+=nums[i];
                rsum+=nums[j];
            }
        }
        if(i==j)
            return i;
        else   
            return -1;
    }
};

为了求出一个通用的办法，需要找出共性，中心点两边的元素和相等，一旦出现一个元素，两边的和相等，那么这个元素就是中心点

为了防止出现[1,2,3,1]中误以为元素2是中心点的情况，需要判断中心点元素加上两边元素和是不是数组的和，也就是2 * sum + nums[i] == total

找到共性

执行流程

  1. 求出数组和
  2. 遍历数组元素，查看是否有2 * sum + nums[i] == total的元素，如果有的话此元素就是中心点，直接返回即可

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int total=accumulate(nums.begin(),nums.end(),0);
        int sum=0;
        for(int i=0;i<nums.size();++i){
            if(2*sum+nums[i]==total){
                return i;
            }
            sum+=nums[i];
        }
        return -1;
    }
};

总结

需要找到题目的关键点，抽象成代码去解决问题，本题中要注意到中心点两边的元素和相等

也就是两边的和加上中心点的元素就是整个数组的和