题目

724. 寻找数组的中心下标

答案

方法一：
暴力求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
    int i = 0;
    for(i=0;i<nums.size();i++)
    {
        int left_sum = 0;
        int right_sum = 0;
        for(int j=0;j<i;j++)
        {
            left_sum += nums[j];
        }
        for(int k=i+1;k<nums.size();k++)
        {
            right_sum += nums[k];
        }
        if(left_sum == right_sum)
        {
            return i;
        }
    }
        return -1;
    }
};

方法二：
前缀和：记数组的全部元素之和为sum，当遍历到第 i 个元素时，设其左侧元素之和为 left_sum，则其右侧元素之和为 total−nums[i] −sum。左右侧元素相等即sum=total−nums[i]−left_sum，即 2×sum+nums[i] =total。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum = accumulate(nums.begin(),nums.end(),0);
        int left_sum = 0;
        for(int i=0;i<nums.size();i++)
        {
            if(2*left_sum+nums[i]==sum)
            {
                return i;
            }
            left_sum+=nums[i];
        }
        return -1;
    }
};

__END__