LeetCode每日一题之 寻找数组中心下标

题目介绍：

题目链接：. - 力扣（LeetCode）

算法原理:

这道题仍然可以使用前缀和的思想来求解，不理解基础前缀和模板的可以看我前面的博客，上图中0-2号位元素的和可以很好地用前缀和数组求出，而后面4-5号位元素则需要利用前缀和的变种----后缀和，利用同样的原理构建出后缀和数组，也可以很好求出，4-5号位元素的和。

这里的前缀和数组要进行一些修改，从题干中可以注意到，它求和时是不需要加上中心下标对应的元素的，所以我们创建前缀和f数组,后缀和g数组：

f[i]表示nums数组[0~(i-1)]区间所有元素的和。f[i]=f[i-1]+nums[i-1] 

g[i]表示nums数组[(i+1)~(n-1)]区间所有元素的和。g[i]=g[i+1]+nums[i+1]

使用前缀和，后缀和数组：

有了前缀和数组 和 后缀和数组后这道题就容易多了，我们只需从左往右遍历一遍数组，当f[i]==g[i]时，我们就返回i，循环完后，没找到就返回-1.

代码实现：

C++：

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        //构建前缀和数组和后缀和数组
        vector<int> f(n),g(n);
        int i = 1;
        for(i=1;i<n;i++)
        {
            f[i]=f[i-1]+nums[i-1];
        }
        for(i=n-2;i>=0;i--)
        {
            g[i]=g[i+1]+nums[i+1];
        }
        //使用前缀和数组和后缀和数组
        for(i=0;i<n;i++)
        {
            if(f[i]==g[i])
            {
                return i;
            }
        }
        return -1;
    }
};