文章目录
- 题目链接：
- 题目描述：
- 解法
- C++ 算法代码：
- 图解
题目链接：
724. 寻找数组的中心下标
题目描述：
解法
暴力枚举：
每次枚举一个下标，就左边加一遍，右边加一遍。
前缀和思想：
f：前缀和数组 这里面f[i]表示：[0,i-1]区间所有元素的和
g：后缀和数组 这里面g[i]表示：[i+1,n-1]区间所有元素的和
f[i]=f[i-1]+nums[i-1]
g[i]=g[i+1]+nums[i+1]
然后这题要找中心下标，所以，从0~n-1找i，使得f[i]==g[i]
C++ 算法代码：
class Solution {public:int pivotIndex(vector<int>& nums) {// lsum[i] 表示：[0, i - 1] 区间所有元素的和// rsum[i] 表示：[i + 1, n - 1] 区间所有元素的和int n = nums.size();vector<int> lsum(n), rsum(n);// 预处理前缀和后缀和数组for(int i = 1; i < n; i++)lsum[i] = lsum[i - 1] + nums[i - 1];for(int i = n - 2; i >= 0; i--)rsum[i] = rsum[i + 1] + nums[i + 1];// 判断for(int i = 0; i < n; i++)if(lsum[i] == rsum[i])return i;return -1;}
};
图解
例如：nums = [1, 7, 3, 6, 5, 6]
lsum[3] == rsum[3]，返回3
