Intuition #

這題本質是尋找配對。對於陣列每個數字 x，我們都需尋找陣列中是否存在另個數字 y，使得 x + y = target。 換句話說，我們是在找 target - x 是否存在。

• 暴力解：最直觀的是檢查每對數字組合。這需要兩層迴圈，效率較低
• 空間換時間：為加速查找，我們可以用 Hash Table (雜湊表)。Hash Table 可以在O(1)內判斷一個值是否存在，並存取其索引

Approaches #

1: Brute Force #

• 概念: 用兩層迴圈，對於每個 nums[i]，檢查後面的每個 nums[j] 是否滿足 nums[i] + nums[j] == target
• 時間複雜度: O(n²) - 對於每個元素，我們都要遍歷剩餘陣列
• 空間複雜度: O(1) - 不需要額外儲存空間

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        for (i in nums.indices) {
            // 從 i + 1 開始，避免重複計算和自我匹配
            for (j in i + 1 until nums.size) {
                if (nums[i] + nums[j] == target) {
                    return intArrayOf(i, j)
                }
            }
        }
        throw IllegalArgumentException("No solution found")
    }
}

⭐2: One-Pass Hash Table #

• 概念: 我們只需遍歷陣列一次。在遍歷過程中，對於每個數字 num：
  1. 計算它需要的補數 complement = target - num
  2. 檢查 Hash Map 中是否已存有這個 complement
  3. 如果有，直接返回當前索引和 complement 的索引
  4. 沒有，將當前數字 num 和它的索引存入 Map 中，供後面的數字查找
• 時間複雜度: O(n) - 我們只遍歷陣列一次，Hash Map 的查找與插入平均為 O(1)
• 空間複雜度: O(n) - 最壞情況下，我們需要儲存 n 個元素在 Map 中

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        // Key: 數字數值, Value: 該數字的索引
        val map = HashMap<Int, Int>()

        for ((i, num) in nums.withIndex()) {
            val complement = target - num

            // 檢查補數是否已經在 Map 中
            if (map.containsKey(complement)) {
                // map[complement] 是先前的索引，i 是當前的索引
                return intArrayOf(map[complement]!!, i)
            }

            // 將當前數字與索引存入 Map
            map[num] = i
        }

        throw IllegalArgumentException("No solution found")
    }
}

題目保證「恰好有一解」，因此不需處理無解或多組解的情況。如果沒有這個保證，則需要額外的錯誤處理邏輯。

補充：Two-Pass Hash Table 雖然 One-Pass 是最佳解，但 Two-Pass 的概念也很容易理解：先跑一次迴圈把所有數字存入 Map，再跑第二次迴圈查找補數。 相比之下，One-Pass 更簡潔且只需一次遍歷。

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = HashMap<Int, Int>()
        // 第一次遍歷：建立索引
        for ((i, num) in nums.withIndex()) {
            map[num] = i
        }
        // 第二次遍歷：查找補數
        for ((i, num) in nums.withIndex()) {
            val complement = target - num
            // 確保找到的不是自己 (i != map[complement])
            if (map.containsKey(complement) && map[complement] != i) {
                return intArrayOf(i, map[complement]!!)
            }
        }
        throw IllegalArgumentException("No solution found")
    }
}

🔑Takeaways #

• 資料結構選擇：當題目涉及「尋找配對」或「檢查存在性」且對時間複雜度有要求時，Hash Map 通常是首選
• 邊界條件：在 Two-Pass 解法中，須小心不要配對到自己（例如 target = 6, nums = [3, 2, 4]，不能返回 [0, 0]）。 One-Pass 解法自然地避開了這問題，因為在查找時，當前數字還沒被放入 Map 中