有關(guān)哈希表的LeetCode做題筆記，Python實(shí)現(xiàn)

1. 兩數(shù)之和 Two Sum

LeetCodeCN 第1題鏈接

第一種方法：用哈希表，時(shí)間復(fù)雜度是O(n)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i in range(len(nums)):
            if nums[i] in dic:
                return [dic[nums[i]], i]
            else:            
                dic[target - nums[i]] = i

第二種方法：暴力兩重遍歷，這樣時(shí)間復(fù)雜度是O(n^2)，在LeetCode里提交會(huì)超時(shí)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

下一題：15. 三數(shù)之和 3Sum