发表于 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

• LC 题目链接