Yifans_Z's Blog.

寻找数组中轴索引

字数统计: 189阅读时长: 2 min
2019/03/06 Share

find-pivot-index

将 pivot 索引定义为:左边的数字之和等于索引右边的数字之和。

Input:
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation:
1 + 7 + 3 = 5 + 6

Input:
nums = [1, 2, 3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

Note:

  • The length of nums will be in the range [0, 10000].
  • Each element nums[i] will be an integer in the range [-1000, 1000].

关键点

  • 动态规划
  • 数组的和 - 中轴数 = 中轴数左边数组的和 * 2

解答

func findPivot(_ array: [Int]) -> Int {
// 数组和
let sum = array.reduce(0, +)
// 左侧数组和
var leftSum = 0
for (key, value) in array.enumerated() {
if sum - value == leftSum * 2 {
return key
}
leftSum += value
}
return -1
}

let array = [1, 7, 3, 6, 5, 6]
search(array) // 3

Reference:

– EOF –

CATALOG
  1. 1. 关键点
  2. 2. 解答