LeetCode 筆記 - 1. Two Sum

Posted on

題目在此 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

也許你也會想看看