【Swift 算法】Two Sum 問題：從暴力解法到最優解法的演進

本文通過“Two Sum”問題，帶你了解如何從最直觀的暴力解法，逐步優化到高效的哈希表解法，并對兩者進行對比，適合算法入門和面試準備。

---

💡 問題描述

給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 的那兩個整數，并返回它們的數組下標。

你可以假設每種輸入只會對應一個答案。
不能使用同一個元素兩次。

---

🪓 解法一：暴力枚舉（Brute Force）

🧠 思路：

• 使用兩層循環，枚舉所有可能的兩兩組合。
• 判斷它們的和是否等于 target。
• 一旦找到即返回。

💻 代碼實現：

func twoSumBruteForce(_ nums: [Int], _ target: Int) -> [Int] {for i in 0..<nums.count {for j in i + 1..<nums.count {if nums[i] + nums[j] == target {return [i, j]}}}return []
}

? 時間復雜度：

• O(n2)：兩層循環遍歷所有組合。

?? 空間復雜度：

• O(1)：只用了常量空間。

? 示例：

let nums = [2, 7, 11, 15]
let target = 9
print(twoSumBruteForce(nums, target)) // 輸出: [0, 1]

---

? 解法二：哈希表（最優解法）

🧠 思路：

• 用一個字典記錄“元素值 ? 索引”。
• 遍歷數組時，計算目標值與當前元素的差值 complement = target - num。
• 判斷這個差值是否已經出現在字典中，如果是，說明找到了。

💻 代碼實現：

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {var numToIndex = [Int: Int]()for (index, num) in nums.enumerated() {let complement = target - numif let complementIndex = numToIndex[complement] {return [complementIndex, index]}numToIndex[num] = index}return []
}

? 時間復雜度：

• O(n)：只遍歷一遍數組，每次查找/插入都是常數時間。

?? 空間復雜度：

• O(n)：用了一個哈希表來存儲元素。

? 示例：

let nums = [2, 7, 11, 15]
let target = 9
print(twoSum(nums, target)) // 輸出: [0, 1]

---

📊 總結對比

解法	時間復雜度	空間復雜度	特點
暴力解法	O(n2)	O(1)	簡單易懂，適合初學者
哈希表解法	O(n)	O(n)	性能更高，適合大數據、面試場景

---