題目敘述

給定一個整數陣列 nums 和一個整數 target，請找出陣列中兩個數字的索引值，使得這兩個數字加總起來剛好等於 target。

• 每筆測資保證有且只有一組解。
• 同一個元素在答案中不能重複使用。

解題思路

對於沒接觸過這類問題的人來說，第一直覺可能是使用雙層迴圈暴力解法，嘗試所有可能的數對來找出符合條件的組合：

n = len(nums)
for i in range(n):
    for j in range(i + 1, n):
        if nums[i] + nums[j] == target:
            return [i, j]

然而，這樣的解法時間複雜度為 $O(n^2)$，當陣列長度達到 $10^4$ 時，效率將無法接受。

如何優化至 $O(n)$？

為了在一次遍歷中完成搜尋，我們可以使用一個字典來記錄數字與其對應的索引。這種做法的核心概念是：

• 當遍歷到第 i 個數字 num 時，我們需要檢查字典中是否存在 target - num，也就是另一個能湊出 target 的數字。
• 如果有，代表之前已經遇過這個「互補數」，現在找到配對了。
• 否則，我們將當前的「互補數 target - num」與當前索引記錄進字典中，等待未來可能的配對。

程式碼實作：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_dict = {}  # 用來儲存需要的補數與其對應的索引

        for i, num in enumerate(nums):
            if num in num_dict:
                return [num_dict[num], i]
            else:
                num_dict[target - num] = i

        return []

時間與空間複雜度分析

• 時間複雜度（Time Complexity）：$O(n)$

  • 我們僅需遍歷 nums 一次，每次操作包含查找與插入 dict，這些操作平均為 $O(1)$。

• 空間複雜度（Space Complexity）：$O(n)$

  • 最壞情況下，字典會存下 n 個鍵值對（所有元素的互補數）。