基本資訊

• 難度： Easy
• 網址： https://leetcode.com/problems/find-pivot-index/

資料結構與演算法

• Prefix Sum

題意

給予一個整數陣列 nums ，請找出一個轉折點，並回傳轉折點的 index 。

轉折點：當左邊（不包含自己）元素的總和等於右邊（不包含自己）元素的總和，當前的自己稱為轉折點。

當找不到轉折的時候請回傳 -1

想法

如果要有效率地在走訪途中就能夠及時比較，就必須

• 先計算整個陣列的總和 (O(n))
• 再走訪一次，比較左邊和右邊的總和 (O(n))
  • 左邊：宣告一個變數邊走訪邊加總，就能夠知道總和了
  • 右邊：陣列總和 - 當前元素 - 左邊
• 結束運算①：當左邊和右邊相等，就回傳當前的索引 (index)
• 結束運算②：走訪完成都沒有相等的話，就回傳 -1

程式碼

class Solution {
    func pivotIndex(_ nums: [Int]) -> Int {
        let sum = nums.reduce(0) { $0 + $1 }
        var left = 0
        
        for (index, num) in nums.enumerated() {
            if left == sum - left - num { return index }
            left += num
        }
        
        return -1
    }
}

執行結果

• Runtime: 109 ms (Beats 74.52%)
• Memory: 14.5 MB (Beats 18.27%)

複雜度分析

令 n 為陣列的長度

結語

以上，就是今天的 LeetCode in Swift ，

如果有什麼問題和回饋歡迎留言一起討論，今天就到這裡，明天見！