給定整數陣列
nums和整數target，回傳兩個數字的索引，使它們的和等於target。每組輸入恰好有一個解，且同一元素不能使用兩次。
Example:
Input: nums = [2,7,11,15], target = 9 Output: [0,1]
Intuition
TIP
核心思路：看到「兩數之和」就想到用 Hash Map 存已遍歷的數，O(1) 查找補數 target - num。
- 對每個數字
x，問題轉化為「陣列中是否存在target - x」 - 暴力法需要兩層迴圈 O(n^2)，用 Hash Map 可以將查找加速到 O(1)
- One-Pass 技巧：邊遍歷邊存入 Map，查找時當前數字還沒被放入，自然避開「配對到自己」的問題
Approaches
1. Brute Force — O(n^2) / O(1)
- Idea: 兩層迴圈，對每個
nums[i]檢查後面的每個nums[j]是否滿足nums[i] + nums[j] == target - Time:
O(n^2)- 每個元素都要遍歷剩餘陣列 - Space:
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 — O(n) / O(n)
- Idea: 遍歷一次陣列，對每個數字計算補數
complement = target - num，若補數已在 Map 中則回傳，否則將當前數字存入 Map - Time:
O(n)- 只遍歷陣列一次，Hash Map 查找與插入平均 O(1) - Space:
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")
}
}WARNING
題目保證「恰好有一解」，因此不需處理無解或多組解的情況。如果沒有這個保證，則需要額外的錯誤處理邏輯。
Note: 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 配對查找的經典入門題
- Key trick: 「空間換時間」——用 Hash Map 將 O(n) 查找降到 O(1)；One-Pass 邊查邊存的技巧可推廣到許多配對問題