724. 寻找数组的中心下标 - 力扣(LeetCode)
解法:前缀和+后缀和
思路:要看一个数是不是中心下标,就看他前面数的和 与 后面数的和 相不相等。
1.i前面数的和,是[0,i-1] 的前缀和,i后面数的和,是[i+1,n-1]的后缀和。
f[i] = f[i-1] + nums[i-1]
2.后缀和(g) 与前缀和(f)差不多:只是倒着来的。
g[i] = g[i+1] + nums[i+1]
细节问题
1.边界情况,如示例三,中心下标在最左端/最右端,那么此时所在位置的前缀/后缀和 = 0
2.前缀和,正着遍历原数组;后缀和,倒着遍历原数组。
3.前缀和 /后缀和 遍历时,越过1 / n-1 ,原因是求和公式会越界。
class Solution
{
public:int pivotIndex(vector<int>& nums) {//1.构造前缀和数组int n = nums.size();vector<int> f(n);f[0] = 0;for(int i = 1;i<n;i++)f[i] = f[i-1] + nums[i-1];//2.构造后缀和数组vector<int> g(n);g[n-1] = 0;for(int i = n-2;i>=0;i--)g[i] = g[i+1] + nums[i+1];//3.使用for(int i = 0;i<n;i++){if(f[i] == g[i])return i;}return -1;}
};