链接
https://leetcode-cn.com/problems/find-pivot-index/
耗时
解题：7 min
题解：11 min
题意
给定一个整数类型的数组 nums，请编写一个能够返回数组 “中心索引” 的方法。
我们是这样定义数组 中心索引 的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。
思路
从左到右遍历，假设以当前元素为中心索引，检查中心索引的左侧所有元素相加的和是否等于右侧所有元素相加的和，是则返回当前元素位置，否则继续检查下一个元素。
求前缀和是为了：在离线情况下，一趟遍历O(n)后，以O(1)的速度快速求数组中任意一段区间的和。
时间复杂度：
O
(
n
)
O(n)
O(n)
AC代码
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int n = nums.size();
vector<int> sum(n+1, 0);
for(int i = 1; i <= n; ++i) {
sum[i] = sum[i-1] + nums[i-1];
}
for(int i = 1; i <= n; ++i) {
int suml = sum[i-1] - sum[0];
int sumr = sum[n] - sum[i];
if(suml == sumr) return i-1;
}
return -1;
}
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
