将 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
References
– EOF –