正文
算法:
既然需要找到这个中心的位置,那么,首先应该知道每一个位置的和是多少,这样的话,我们就可以设计出来一个数组,专门保存我们当前的累加和,方便与后续的操作。
时间复杂度:O(N)
空间复杂度:O(N)
最后的代码:
class Solution724: def pivotIndex(self, nums: List[int]) -> int: res = -1 n = len(nums) if n == 0: return -1 elif n == 1: return 0 elif n < 3: return -1 else: sum_list = [0 for i in range(n)] sum_list[0] = nums[0] for j in range(1, n): sum_list[j] = sum_list[j - 1] + nums[j] if sum_list[n - 1] == sum_list[0]: return 0 for j in range(1, n - 1): if sum_list[j - 1] == sum_list[n - 1] - sum_list[j]: return j if sum_list[n - 2] == 0: return n - 1 return res
最后一定不要忘记边界值哈!!!!