题目:
给定一个整数类型的数组 nums,请编写一个能够返回数组“中心索引”的方法。
我们是这样定义数组中心索引的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引,那么我们应该返回 -1。如果数组有多个中心索引,那么我们应该返回最靠近左边的那一个。
示例 :
输入: nums = [1, 7, 3, 6, 5, 6], 输出: 3
输入: nums = [1, 2, 3], 输出: -1
说明:
nums 的长度范围为 [0, 10000]。任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。
-----------------------------------------------------------------------
解法1:常规做法,超时
class Solution(object):
def pivotIndex(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 3:
return -1
for i in range(len(nums)):
if sum(nums[:i]) == sum(nums[i+1:]):
return i
return -1
解法2:先求出所有数的总和,然后遍历数组,如果遍历数的左边*2 + 遍历数 == 总和 , 遍历数即为中心索引。
class Solution:
def pivotIndex(self, nums):
"""
:type nums: List[int]
:rtype: int
# 计算数组的和
res = sum(nums)
# 初始化左边的和
lsum = 0
for i, num in enumerate(nums):
if lsum * 2 + num == res:
return i
lsum += num
return -1
参考:
https://blog.csdn.net/maka_uir/article/details/86764051
https://blog.csdn.net/wangsiyu34567/article/details/82964413
https://blog.csdn.net/huhehaotechangsha/article/details/86513651