JZX轻语：简
LeetCode 724 - 寻找数组的中心索引
发表于2024年07月08日
比较简单的前缀和题目，但有个优化点值得记录下。该题目可以套用前缀和模板做法，即计算双侧前缀和，先记录一遍前缀和，然后再反向遍历一遍数组，如果当前前缀和和后缀和相等，则返回当前索引即可。但是这样的时间复杂度是O(n)。有一个更好的做法，可以在前缀和计算的过程中直接判断是否满足条件，这样可以减少空间开销。具体做法是，先计算出数组的总和total，然后遍历数组，如果当前前缀和prefix(不包括当前的数)等于total - prefix - nums[i]，则返回当前索引即可。这样可以做到O(1)的空间复杂度，但还是需要两次遍历，时间复杂度为O(n)。
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
sum_ = sum(nums)
prev_sum = 0
for i, num in enumerate(nums):
if prev_sum == sum_ - prev_sum - num:
return i
prev_sum += num
return -1之前的做法：
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
prev_sum = list(itertools.accumulate(nums))
for i, num in enumerate(nums):
left = prev_sum[i] - num
right = prev_sum[-1] - prev_sum[i]
if left == right:
return i
return -1