題目描述:給定一個整數陣列 nums 與目標值 target,找出兩個數字的索引,使它們相加等於 target。
解題思路:暴力法需要 O(n²) 時間逐一比對,但可以用雜湊表將時間複雜度降至 O(n)。遍歷陣列時,對於每個元素 nums[i],計算它的補數 complement = target - nums[i]。若補數已在雜湊表中,直接回傳兩個索引;否則將 nums[i] 存入雜湊表。這樣只需一次遍歷,以空間換取時間。
時間複雜度:O(n) — 單次遍歷,每次雜湊表查詢為 O(1)。
空間複雜度:O(n) — 雜湊表最多儲存 n 個元素。
1. Create empty hash map: value -> index 2. For each index i, value num in nums: a. Compute complement = target - num b. If complement exists in map, return [map[complement], i] c. Else store map[num] = i 3. Return [] (guaranteed solution exists per problem)
暴力法 O(n²):嵌套迴圈逐一檢查所有配對 — 簡單但在 n 較大時過慢。
排序 + 雙指標 O(n log n):排序 (value, index) 配對,雙指標從兩端移動。失去原始索引,額外空間為 O(1)(不計排序)。比雜湊表方法複雜,且時間複雜度不更優。