LeetCode 筆記 - 1. Two Sum

Posted on 標籤
針對 LeetCode 第 1 題，探討如何在數列中快速找出相加等於目標值的兩個數字。本文解析如何運用哈希表（Hash Map）記錄已遍歷過的數字及其索引，將搜尋複雜度從暴力解的 O(N^2) 優化至線性 O(N)，是理解空間換取時間的經典案例。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 1. Two Sum

如何快速的在一個數列找到兩個數目字相加等於目標數？

解題思維

思維是使用 map 將看過的數字當作 index 存起來
只要檢查需要的數字存不存在在過去看過的數字有沒有在 map 裡
這樣在 Time complexity 就可以在 O(n) 解決問題

Time complexity: O(n)

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        if not nums:
            return None
        
        seen = {}
        for i, v in enumerate(nums):
            
            if target - v in seen:
                return [i, seen[target - v]]
            
            seen[v] = i

也許你也會想看看