[LeetCode] 1. Two Sum 題解
給定一個整數陣列 nums
和一個目標數字 target
,要求返回陣列中兩個數字的 下標 ,且這兩個數字加起來等於目標數字 target
你可以假設每組輸入將會有一個解決方案,且陣列中同一個數字只能使用一次
例子:
輸入 nums = [2, 7, 11, 15], target = 9, 因為 nums[0] + nums[1] = 2 + 7 = 9, 所以 return [0, 1]。 複製程式碼
問題難度
Easy
解題思路
期望遍歷一遍陣列,就可以找到兩個符合條件的數字,遍歷過程中,每讀到一個數字,需要完成兩個動作:
- 查詢「補數集合」,判斷該數字的「補數」(目標數字減去該數)是否存在,如果存在,則返回補數和該數的下標
- 如果不存在,那麼該數很可能是別的數的「補數」,將該數和下標放入「補數集合」中
可以看到「補數集合」是這裡的關鍵,它要以儘可能快的速度完成:
- 查詢某個補數是否存在
- 插入一個補數
這兩個操作。
而我們都知道,對於這種需求,有一種資料結構可以達到的時間複雜度,那就是雜湊表,說到這裡,我們就可以動手寫程式碼了:
class Solution(object): def twoSum(self, nums, target): complements = {} for i, x in enumerate(nums): if target - x in complements: return [complements[target - x], i] complements[x] = i 複製程式碼
以上, complements
是我們的「補數集合」,在 Python 中,字典(dict)資料結構就是用雜湊表實現的,所以這裡 complements
就定義為一個字典。
第 4 行我們依次遍歷陣列
第 5、6 行用來判斷當前數的「補數」是否存在,如果存在則返回「補數」所在的下標和當前數的下標
第 7 行是在「補數」不存在的情況下,將當前數作為其他數的「補數」,連同下標一起插入到「補數集合」中
於是,上面程式碼就實現了通過遍歷一次陣列,就可以找到符合條件的兩個數的下標,時間複雜度為。