LCR 012. 寻找数组的中心下标

Leetcode题目:前缀和

给你一个整数数组 nums ,请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标,应该返回 最靠近左边 的那一个。如果数组不存在中心下标,返回 -1 。

示例 1:

输入:nums = [1,7,3,6,5,6]
输出:3
解释:
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ,
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ,二者相等。

示例 2:

输入:nums = [1, 2, 3]
输出:-1
解释:
数组中不存在满足此条件的中心下标。

示例 3:

输入:nums = [2, 1, -1]
输出:0
解释:
中心下标是 0 。
左侧数之和 sum = 0 ,(下标 0 左侧不存在元素),
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

提示:

  • 1 <= nums.length <= 104
  • -1000 <= nums[i] <= 1000

注意:本题与主站 724 题相同: https://leetcode-cn.com/problems/find-pivot-index/

解题思路

前缀和

还剩两道前缀和的简单题,另一道貌似要用贪心求局部最优解,但我现在贪心用的还不熟,所以先不写那道。

但是这道之前写过了,刚好最近在学go,所以就用go重新写了一下,思路还是一样的。

不过有那么一瞬间在想return i那块的sum[i+1]会不会溢出,但想了下i+1最大就是n,也就是sum[n],所以还是不会溢出的。只能说这里还没完全掌握才会怀疑。

而且必须要写return,因为返回的是第一次出现的中心下标。等搞完贪心再写另一道前缀和+贪心的题。

func pivotIndex(nums []int) int {
    n:=len(nums)
    sum:=make([]int,n+1)
    index:=-1
    for i:=0;i<n;i++{
        sum[i+1]=sum[i]+nums[i]
    }
    for i:=0;i<n;i++{
        if sum[n]-sum[i]==sum[i+1]{
            return i
        }
    }
    return index
}
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x