Find Pivot Index
给你一个整数数组 nums。中心索引是指左侧所有值的和等于右侧所有值的和的索引。中心索引处的值不属于任何一侧，没有值的一侧总和为 0。
返回最左侧的中心索引；如果没有中心索引，则返回 -1。
函数
- numsinteger-array
- 要平衡的整数数组
- 返回值integer
- 最左侧的枢轴索引；如果不存在，则为 -1
约束条件
1 ≤ nums.length ≤ 104-1000 ≤ nums[i] ≤ 1000
示例
- 输入
- nums = [3, 1, 5, 2, 2]
- 输出
- 2
- 解释
- 在索引 2 处，左侧的和 3 + 1 = 4 与右侧的和 2 + 2 = 4 相等。索引 0 处左侧为 0，右侧为 10；索引 1 处左侧为 3，右侧为 9，因此 2 是最左边的支点。
- 输入
- nums = [1, 2, 3]
- 输出
- -1
- 解释
- 这三个候选项分别是 0 对 5、1 对 3 和 3 对 0。没有任何一个索引能实现平衡，因此答案是
-1。
- 输入
- nums = [4, -4, 9]
- 输出
- 2
- 解释
- 在索引 2 处，左侧的和是 4 + (-4) = 0，右侧为空，因此和也为 0。最后一个索引可以作为支点。
进阶
你能否在每个值只读取一次的情况下找到最左侧的枢轴，而不先计算总和？这会占用多少内存？
提示
逐个打开提示，每个都会多透露一点。
检查一个索引需要计算两个总和：它之前的值之和和它之后的值之和。每个索引都重新计算这些总和，会重复几乎所有工作。索引
i的两个总和与索引i+1的两个总和有什么关系？向右移动一步，就把
nums[i]加到左侧总和中。一旦知道整个数组的总和，就可以根据左侧总和得出右侧总和：用总和减去左侧总和，再减去nums[i]。先把整个数组的值加起来。然后从左向右遍历，同时累加左侧的和。在每个索引处，将左侧的和与总和减去左侧的和再减去当前值进行比较；第一次匹配时返回该索引，只有在比较之后才将当前值加到左侧的和中。如果循环结束，返回 -1。
题解
在每个索引处重新计算两个总和，时间开销为 O(n²)。左侧总和每一步增加一个值，右侧总和则是总和减去左侧后剩下的部分。因此，先遍历一次计算总和，再遍历一次并持续更新左侧总和，就能找到最左边的枢轴索引，而且只需在内存中保存两个数字。
将每个索引处两侧的值相加
结果正确，但无法在最大的测试中运行完毕
思路
对每个索引，分别将它前面和值后面的值相加，再进行比较。从左到右尝试索引，会让第一个匹配项成为最左边的枢轴。在任一边缘，一个循环会运行 0 次，且它的和保持为 0，这就是 [4, -4, 9] 返回 2 的原因。
每个索引都会把其他 n-1 个值相加。对于 10,000 个值，这接近 1 亿次加法，其中大多数都在重复计算前一个索引已经算过的和。
算法
- 遍历
nums的每个索引i。 - 将
nums[0]到nums[i-1]的值相加，作为左侧总和。 - 将
nums[i+1]到最后一个值相加，作为右侧总和。 - 如果两个总和相等，返回
i。 - 如果没有匹配的索引，返回 -1。
def pivotIndex(nums):
n = len(nums)
for i in range(n):
left = 0
for j in range(i):
left += nums[j]
right = 0
for j in range(i + 1, n):
right += nums[j]
if left == right:
return i
return -1前缀和数组
思路
前缀和数组只需累加一次。设 prefix[k] 表示前 k 个值的和，其中 prefix[0] = 0；对于 [3, 1, 5, 2, 2]，结果是 [0, 3, 4, 9, 11, 13]。索引 i 左侧的和是 prefix[i]，右侧的和是 prefix[n] - prefix[i+1]。在索引 2 处，左侧的和为 4，右侧的和为 13 - 9 = 4，因此这里是中心索引。
只需遍历一次即可构建数组，每次检查都只需常数时间：时间复杂度为 O(n)，内存中额外占用 n+1 个数值。
算法
- 创建长度为
n+1的prefix，并设置prefix[0] = 0。 - 填充它：
prefix[k+1] = prefix[k] + nums[k]。 - 对于每个索引
i，将左侧总和记为prefix[i]，将右侧总和记为prefix[n] - prefix[i+1]。 - 返回它们相等时第一个
i，如果循环结束后仍未找到，则返回 -1。
def pivotIndex(nums):
n = len(nums)
# prefix[k] is the sum of the first k values.
prefix = [0] * (n + 1)
for k in range(n):
prefix[k + 1] = prefix[k] + nums[k]
for i in range(n):
left = prefix[i]
right = prefix[n] - prefix[i + 1]
if left == right:
return i
return -1总和与不断累加的左侧和
思路
在索引 i 处，前缀和方法会读取 prefix[i]、prefix[i+1] 和 prefix[n]。最后一个值是总和，它始终不变；另外两个值是遍历过程中可以逐步累加的和。因此，保留总和和一个左侧和即可，不必使用数组。
每个值都在 i 的左侧、位于 i 处或在 i 的右侧，因此右侧和为 total - left - nums[i]。比较之后再把 nums[i] 加到 left，这样左侧和就不会包含你正在检查的值。在第一个示例中，总和是 13，索引 2 处的值是 4，而 13 - 4 - 5 = 4。
两次遍历需要 O(n) 时间，两个数需要 O(1) 空间。
算法
- 将每个值累加到
total中。 - 将
left设为 0。 - 对于每个索引
i，如果left等于total - left - nums[i]，则返回i。 - 否则，将
nums[i]加到left，然后继续。 - 如果循环结束，则返回 -1。
def pivotIndex(nums):
total = sum(nums)
left = 0
for i, value in enumerate(nums):
# Everything that is not on the left and not nums[i] is on the right.
if left == total - left - value:
return i
left += value
return -1
易错点和边界情况
- 在比较之前把
nums[i]加到左侧总和中。这样左侧就包含了支点值，而[3, 1, 5, 2, 2]不再能找到索引 2。 - 将右侧计算为
total - left。这样会把nums[i]也算在右侧，因此还要减去它。 - 跳过索引 0 或最后一个索引。空侧的总和为 0，因此
[1, -1, 1]返回 0，[4, -4, 9]返回 2。 - 返回最后一个匹配项。在
[0, 0, 0]中，每个索引都能平衡，因此答案是 0。 - 忘记 Lua 和 R 的数组从 1 开始。返回
i-1，这样答案就是从 0 开始的索引。
常见问题3
查找枢轴索引的时间复杂度是多少？
总和与运行和的解法需要 O(n) 时间，一次遍历数组求和，一次遍历数组进行扫描，并且只需要 O(1) 的额外空间。在每个索引处重新计算两侧的总和需要 O(n²) 时间。
能用双指针解决查找枢轴索引的问题吗？
不一定可靠。从两端开始扫描，并始终扩展较小的一侧，这种做法假设添加一个值会让这一侧变大。这里的值可能低至 -1000，因此一侧在扩展时也可能变小，指针可能会越过真正的支点。
只有一个元素的数组的中心索引是什么？
它是 0。唯一元素的两侧都是空的，空的一侧总和为 0，所以两侧相等。运行总和的答案在第一次比较时返回 0。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def pivotIndex(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [3, 1, 5, 2, 2]
预期输出
2