哈希表.md

[TOC]

数组中两数和为给定值

Two Sum (Easy)

可以先对数组进行排序，然后使用双指针法或二分查找法，时间复杂度为 O(NlogN)，空间复杂度为 O(1)。

用 HashMap 储存数组元素和索引的映射，访问 nums[i] 时，判断 HashMap 中是否存在 target - nums[i]。时间复杂度为 O(N)，空间复杂度为 O(N)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i, num in enumerate(nums):
            index = hashmap.get(target - num)
            if index is not None:
                return [i, index]
            hashmap[num] = i

判断数组是否含有重复元素

Contains Duplicate (Easy)

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        hashmap = {}
        for num in nums:
            if hashmap.get(num):
                return True
            hashmap[num] = 1

最长和谐序列

Longest Harmonious Subsequence (Easy)

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        hashmap = {}
        for num in nums:
            hashmap[num] = hashmap.get(num, 0) + 1
        
        longest = 0
        for num in nums:
            if num+1 in hashmap:
                longest = max(longest, hashmap[num] + hashmap[num+1])
        return longest

最长连续序列

Longest Consecutive Sequence (Hard)

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        hashmap = {}
        for num in nums:
            hashmap[num] = 1
        for num in nums:
            self.forward(hashmap, num)
        return max(hashmap.values())
    
    def forward(self, hashmap: dict, num: int) -> int:
        if hashmap.get(num) is None:
            return 0
        cnt = hashmap.get(num)
        if cnt > 1:
            return cnt
        cnt = self.forward(hashmap, num+1) + 1
        hashmap[num] = cnt
        return cnt