• 難度： Easy
• 網址： https://leetcode.com/problems/two-sum/

鐵人賽的第一天，做為起手式，就先從最簡單的 Two Sum 開始吧！

題意

給予一個陣列 nums 和一個整數 target ，並回傳和等於 target 的兩個索引，並只會有一對索引符合需求。

範例

nums = [2,7,11,15]
target = 9

就需要回傳 2 和 7 的索引：

[0, 1]

1. 直覺解 - 雙迴圈暴力解

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        for leftIndex in 0..<(nums.count - 1) {
            for rightIndex in (leftIndex + 1)..<nums.count {
                if nums[leftIndex] + nums[rightIndex] == target {
                    return [leftIndex, rightIndex]
                }
            }
        }
        return []
    }
}

執行結果

• Runtime: 64 ms (Beats 43.69%)
• Memory: 14.2 MB (Beats 67.58%)

複雜度

令 n 為 nums 的個數

• 時間複雜度： O(n^2)
  • 因為必須走訪兩層的迴圈
• 空間複雜度： O(1)
  • 並沒有多宣告多餘的儲存空間

解說

這個解法很直接，使用兩個 flags leftIndex 和 rightIndex ，走訪邏輯就是外層 leftIndex 逐一走訪到 n - 1 ， rightIndex 則從 leftIndex 往右一格的位置開始尋找，直到找到位置。

缺點

時間複雜度為平方，因此，當 n 為極大值時就有可能會超時。
因此我們要想辦法把降至 O(n)。

2. 邊把期望值算出來並暫存 - Hash Table

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        /// [expectation: Index]
        var expectations = [Int: Int]()
        for (index, num) in nums.enumerated() {
            if let found = expectations[target - num] {
                return [found, index]
            }
            expectations[num] = index
        }
        return []
    }
}

執行結果

• Runtime: 37 ms (Beats 98.36%)
• Memory: 14.2 MB (Beats 82.94%)

複雜度

令 n 為 nums 的個數

• 時間複雜度： O(n)
  • 只需走訪一個單層的迴圈
  • 取用 hash map 的時間複雜度為 O(1)
• 空間複雜度： O(n)
  • 最壞情形之下，需要一個 n-1 的 hash map 來儲存期望值，故為 O(n)

解說

為了要把迴圈降為一格，可以試著邊走訪，邊把想找的值計算出來，將這個期望值 (expectation) 和索引儲存在一格 dictionary 。

當走到下一格的時候，先比對當前的數值有沒有在這個 dictionary 裡，有的話就可以結束處理並回傳。

以 [2, 7] , 9 為例，逐步變化就會如下

# 初始狀態
expectations = [:]() // 為空

Step 1

index -> 0
current -> 2
found index -> expectations[2] 為 nil
expectation -> 7 // 9 - 2
expectations -> [7: 0]

Step 2

index -> 1
current -> 7
found index -> expectations[7] 為 0 -> 回傳 [0, 1]

由於在尋找期望值的階段就找到目標值，因此可以直接中斷運算回傳。

題外話 - LeetCode 的效能影響

在 LeetCode 的 Swift 編譯器中， enumerated() 和傳統的 for index in 0..<nums.count 這樣寫法的差異沒有太大可忽略。

但是根據自己嘗試改寫， guard-let 就會比 if-let 慢，所以如果要追求執行速度可以嘗試不同的寫法。

不過無論是什麼寫法還是要以容易閱讀優先。

比較兩個解法

從數值看來 Hash Map 是較佳解，時間是有時候甚至會是暴力解的一半，而根據 LeetCode 的測試案例，使用的空間基本上沒差別。

結語

原先想想 Two Sum 寫起來應該很簡單，但是詳述思考過程和解說還是會變這麼長，不過作為第一天也算是一個好題材。

明天見！