LeetCode75学习计划-前缀和

算法解题思路很多会借鉴于题解区，如果侵权请联系删除。

本章节知识点为前缀和。

找到最高海拔

题目标签：

• 数组
• 前缀和

题目难度： Easy

题目描述：

有一个自行车手打算进行一场公路骑行，这条路线总共由 n + 1 个不同海拔的点组成。自行车手从海拔为0 的点 0 开始骑行。

给你一个长度为 n 的整数数组 gain ，其中 gain[i] 是点 i 和点 i + 1 的 净海拔高度差（0 <= i < n）。请你返回 最高点的海拔 。

示例：

输入：gain = [-5,1,5,0,-7]
输出：1
解释：海拔高度依次为 [0,-5,-4,1,1,-6] 。最高海拔为 1

解题思路：

• 题目确定是从海拔 0 开始出发的，我们循环 gain， 每一次累加得到的都是当前地点的海拔高度。取最大值即可

代码实现：

func largestAltitude(gain []int) int {
    current := 0
    res := 0
    for _, v := range gain {
        // 当前点的海拔高度
        current += v
        // 更新最终结果
        res = max(current, res)
    }
    return res
}
func max (a, b int) int {
    if a > b {
        return a
    }
    return b
}

寻找数组的中心下标

题目标签：

• 数组
• 前缀和

题目难度： Easy

题目描述：

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

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

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

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

解题思路：

• 求数组所有元素的和为 total，中心下标 i 满足 其左侧的和sum = total - sum - nums[i]

代码实现：

func pivotIndex(nums []int) int {
  // 计算数组的总和
  total := 0
  for _, v := range nums {
    total += v
  }
  // 初始sum为0，因为左侧无元素也看作0 
  sum := 0
  for i, v := range nums {
    // 中心下标的值 + 左侧和 * 2 = 总和
    if sum * 2 + v == total {
      return i
    }
    // 更新左侧和
    sum += v
  }
  // 找不到返回-1
  return -1
}