尋找數組中軸索引

• 2019 年 11 月 8 日
• 筆記

將 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:

• 找到數組中左右兩邊的和相等的 pivot 的下標 Find Pivot Index

– EOF –