1. Two Sum

Easy

Description

給定整數陣列 nums 和整數 target，回傳兩個數字的索引，使它們的和等於 target。每組輸入恰好有一個解，且同一元素不能使用兩次。

Example:

Input: nums = [2,7,11,15], target = 9 Output: [0,1]

Intuition#

核心思路：看到「兩數之和」就想到用 Hash Map 存已遍歷的數，O(1) 查找補數 target - num。

對每個數字 x，問題轉化為「陣列中是否存在 target - x」
暴力法需要兩層迴圈 O(n^2)，用 Hash Map 可以將查找加速到 O(1)
One-Pass 技巧：邊遍歷邊存入 Map，查找時當前數字還沒被放入，自然避開「配對到自己」的問題

Approaches#

1: Brute Force#

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

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        for (i in nums.indices) {
            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#

概念: 遍歷一次陣列，對每個數字計算補數 complement = target - num，若補數已在 Map 中則回傳，否則將當前數字存入 Map
時間複雜度: O(n) - 只遍歷陣列一次，Hash Map 查找與插入平均 O(1)
空間複雜度: O(n) - 最壞情況需儲存 n 個元素

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = HashMap<Int, Int>()

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

            if (map.containsKey(complement)) {
                return intArrayOf(map[complement]!!, i)
            }

            map[num] = i
        }

        throw IllegalArgumentException("No solution found")
    }
}

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

補充：Two-Pass Hash Table

先跑一次迴圈把所有數字存入 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
            if (map.containsKey(complement) && map[complement] != i) {
                return intArrayOf(i, map[complement]!!)
            }
        }
        throw IllegalArgumentException("No solution found")
    }
}

🔑 Takeaways#

Pattern: Two Sum 是 Hash Map 配對查找的經典入門題
關鍵技巧: 「空間換時間」——用 Hash Map 將 O(n) 查找降到 O(1)；One-Pass 邊查邊存的技巧可推廣到許多配對問題