[LeetCode解題攻略] 1. Two Sum

在 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)

解法解析：

1. 使用雜湊表 num_map 來存儲每個數字及其對應的索引。
2. 在遍歷 nums 的過程中，每次計算出當前數字的補數 complement（即 target - num）。
3. 如果補數已經存在於雜湊表中，則返回補數的索引和當前數字的索引。
4. 如果補數不存在，將當前數字和它的索引存入雜湊表，繼續遍歷。

這樣的方式大大減少了運算時間，因為查找哈希表中的元素是 O(1) 的操作。

解法總結

1. 暴力解法：兩重迴圈遍歷所有組合，簡單直觀但效率低，適用於小型數組。
2. 雜湊表解法：用雜湊表記錄元素，通過查找補數來快速解決問題，適合處理大型數組，時間複雜度僅 O(n)。

結論

Two Sum 是一個經典的面試題，能夠考察你對數組遍歷和查找的基本能力。掌握這道題目後，進一步理解如何有效地使用資料結構（如雜湊表）來解決問題，將對其他類似的問題大有幫助。

這道題目不僅測試了程式設計的基礎功底，也是理解資料結構如何在解題中發揮作用的重要一步。希望透過這篇解題教學，能夠幫助你更好地理解 LeetCode Two Sum 的解法，並靈活應用於其他問題中。