0724. 寻找数组的中心下标

[utterances-bot]

0724. 寻找数组的中心下标 | 算法通关手册

724. 寻找数组的中心下标 # 标签：数组 难度：简单 题目大意 # 描述：给定一个数组 nums。 要求：找到「左侧元素和」与「右侧元素和相等」的位置，若找不到

https://algo.itcharge.cn/Solutions/0700-0799/find-pivot-index/

[dhyuk54]

if curr_sum * 2 + nums[i] == sum:

这块没太看明白

[itcharge]

if curr_sum * 2 + nums[i] == sum:

这块没太看明白

这里 sum 是数组中所有元素和，curr_sum 是当前数组左侧元素和。
根据题意，有：左侧元素和 + 当前元素值 = 所有元素和 - 右侧元素和，即 curr_sum + nums[i] == sum - 右侧元素和。
如果当前元素 nums[i] 就是「左侧元素和」与「右侧元素和相等」的位置，那么这里「左侧元素和」就等于右侧元素和，
公式就可以写成：curr_sum + nums[i] == sum - curr_sum，变换一下就是 curr_sum * 2 + nums[i] == sum。

[lcq666666]

还有其他做法么

[enigdata]

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        leftsum = 0

        arr_sum = sum(nums)
        for i in range(len(nums)):
            rightsum = arr_sum - nums[i] - leftsum
            if rightsum == leftsum:
                return i
            leftsum += nums[i]

        return -1

[Is-Grit]

其实没必要全部求和

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        ListLen = len(nums)                    
        Z_N = 0
        Z_S = 0
        MidList = []
        SumNums = sum(nums)
        
        for i in range (ListLen):
            if(Z_S + Z_S == SumNums-nums[i]):
                MidList.append(Z_N)

            Z_S += nums[i]
            Z_N += 1
        if (len(MidList)==0):
            return -1
        else:
            return MidList[0]

[Derek-cny]

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        n=len(nums)
        count=0
        for i in range(n):
            count+=nums[i]
        if count-nums[0]==0:

            return 0
        for i in range(1,n):
            left=0
            right=0
            if i>0:
                for j in range(0,i):
                    left+=nums[j]
                for j in range(i+1,n):
                    right+=nums[j]
                if left==right:
                    return i

        return -1

        我写的不过超时了hhh

[Guangzhengzhong]

这个解法当数组长度为2，有一个数为0的时候解不了

[zhuyjan]

class Solution:
def pivotIndex(self, nums: List[int]) -> int:
length = len(nums)
sumLeft = list()
sumRight = list()
sum = 0
for i in range(length):
sum += nums[i]
sumLeft.append(sum)
sumLeft.insert(0,0)
sum = 0
for i in range(length - 1, -1, -1):
sum += nums[i]
sumRight.append(sum)
sumRight.insert(0,0)
for i in range(length):
if sumLeft[i] == sumRight[length - i - 1]:
return i

    return -1

[zhuyjan]

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        length = len(nums)
        sumLeft = list()
        sumRight = list()
        sum = 0
        for i in range(length):
            sum += nums[i]
            sumLeft.append(sum)
        sumLeft.insert(0,0)
        sum = 0
        for i in range(length - 1, -1, -1):
            sum += nums[i]
            sumRight.append(sum)
        sumRight.insert(0,0)
        for i in range(length):
            if sumLeft[i] == sumRight[length - i - 1]:
                return i

        return -1

[chenxu2002]

class Solution(object):
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sum_left = 0
        sum_right = sum(nums) - nums[0]
        if sum_left == sum_right:
            return 0
        for i in range(1, len(nums)):
            sum_left += nums[i-1]
            sum_right -= nums[i]
            if sum_right == sum_left:
                return i
        return -1

[chenxu2002]

class Solution(object):
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sum_left = 0
        sum_right = sum(nums) - nums[0]
        if sum_left == sum_right:
            return 0
        for i in range(1, len(nums)):
            sum_left += nums[i-1]
            sum_right -= nums[i]
            if sum_right == sum_left:
                return i
        return -1

[Wan-Yifei]

为什么不直接用sum()求和？只需要用一个for loop， 虽然复杂度没变但是会快很多。

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        left = 0
        total_sum = sum(nums)
        for i in range(len(nums)):
            if left == total_sum - left - nums[i]:
                return i
            else:
                left += nums[i]
        return -1

[lcq666666]

  您好，感谢您的提问，我看看了此题，直接使用sum求和，看起来更直观，但实际运行效率差非常多，因为我两边的数都要进行计算和维护，但是实质是右边的数可以通过左边何总数来计算出来，右边没必要再计算和；另外，如果在for里面使用sum函数的话，又增加了复杂度，因为sum的复杂度是O（n），总的复杂度就是O（n的平方）。   祝好 李驰强 李驰强 ***@***.***

[zkc07]

因为数组无序，所以大方向上确实想不出什么好的方法。
还是官方解答比较优雅；sum+ sum + nums[i] = total;
int pivotIndex(int* nums, int numsSize) {
int sum1 = 0;
int sum2 = 0;
for(int i =1;i<=numsSize-1;i++){
sum1 = sum1+nums[i]; // sum 是数组index 1 到 end 的和
}
if(0==sum1){
return 0;
}

for(int i=1;i<=numsSize-1;i++){
    sum2 = nums[i-1] + sum2;
    sum1 = sum1 - nums[i];

    if(sum2 == sum1){
        return i;
    }
}

return -1;

}