在 LeetCode 上，Two Sum 這道題目主要考察如何高效地處理數組和數據查找問題，是面試中常見的問題之一。今天我們將詳細解說這道題目，並提供幾種解題方法。
題目描述
給定一個整數陣列 nums 和一個目標值 target，請你在該陣列中找出和為目標值的那 兩個 整數，並返回他們的索引。你可以假設每種輸入只會對應一個答案，並且你不能重複使用相同的元素。
輸入：nums = [2, 7, 11, 15], target = 9
輸出：[0, 1]
解釋：因為 nums[0] + nums[1] == 9，所以返回 [0, 1]。
解題思路
這道題目的核心是如何在一個數組中找到兩個數字，使它們的和等於 target。常見的解法有以下幾種：暴力解法、使用雜湊表的解法。
1. 暴力解法
最直接的解法就是遍歷數組的每一個元素，並對每個元素再遍歷一次其他元素，來檢查它們是否滿足相加等於 target 的條件。這樣的解法時間複雜度是 O(n^2)，對於小型數組可以使用，但如果數組很大，效率會較低。
程式碼：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
時間複雜度：O(n^2)
空間複雜度：O(1)
這種方法非常簡單，但當 nums 長度較大時，可能會導致效能問題。
2. 使用雜湊表的解法
為了提高效率，我們可以使用雜湊表來記錄已經遍歷過的數字。當我們遍歷每一個數字時，計算出需要的另一個數字，並檢查這個數字是否已經在雜湊表中。如果存在，則說明這兩個數字加起來等於 target，我們可以立即返回它們的索引。
這種方法只需要遍歷一次數組，因此時間複雜度可以降低到 O(n)。
程式碼：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
num_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_map:
return [num_map[complement], i]
num_map[num] = i
時間複雜度：O(n)
空間複雜度：O(n)
解法解析：
- 使用雜湊表
num_map來存儲每個數字及其對應的索引。 - 在遍歷
nums的過程中，每次計算出當前數字的補數complement（即target - num）。 - 如果補數已經存在於雜湊表中，則返回補數的索引和當前數字的索引。
- 如果補數不存在，將當前數字和它的索引存入雜湊表，繼續遍歷。
這樣的方式大大減少了運算時間，因為查找哈希表中的元素是 O(1) 的操作。
解法總結
- 暴力解法：兩重迴圈遍歷所有組合，簡單直觀但效率低，適用於小型數組。
- 雜湊表解法：用雜湊表記錄元素，通過查找補數來快速解決問題，適合處理大型數組，時間複雜度僅 O(n)。
結論
Two Sum 是一個經典的面試題，能夠考察你對數組遍歷和查找的基本能力。掌握這道題目後，進一步理解如何有效地使用資料結構（如雜湊表）來解決問題，將對其他類似的問題大有幫助。
這道題目不僅測試了程式設計的基礎功底，也是理解資料結構如何在解題中發揮作用的重要一步。希望透過這篇解題教學，能夠幫助你更好地理解 LeetCode Two Sum 的解法，並靈活應用於其他問題中。
