哈希表数据结构原理与经典算法题解析

进阶问题要求支持 Unicode 字符（比如中文、特殊符号、大写字母等），此时一个固定长度的数组无法满足，需要用通用哈希表实现，比如 Python 中的 dict。

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    freq = {}
    for c in s:
        freq[c] = freq.get(c, 0) + 1
    for c in t:
        if freq.get(c, 0) == 0:
            return False
        freq[c] -= 1
    return True

题目二：LeetCode 349. 两个数组的交集

主要的难点在于输出结果中的每一个元素一定是唯一的，需要去重。

如果题目没有限制数值的大小，就无法使用数组来做哈希表。另外，如果哈希值比较少，特别分散、跨度非常大，使用数组就造成空间的极大浪费。

def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
    record = dict()
    intersection = []
    for num in nums1:
        record[num] = 0
    for num in nums2:
        if num in record:
            record[num] = 1
    for key, value in record.items():
        if value == 1:
            intersection.append(key)
    return intersection

def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
    st = set(nums1)
    ans = []
    for x in nums2:
        if x in st:
            st.remove(x)
            ans.append(x)
    return ans

题目三：LeetCode 202. 快乐数

1. 根据题目可以得出主要有两种情况，一种是找到 sum 为 1，一种是 sum 开始循环出现。所以这道题目使用哈希法，记录每次 sum 的值，如果遇到重复值则 return False，否则一直计算，直到 sum 为 1，return True。

def isHappy(self, n: int) -> bool:
    result = set()
    while n != 1:
        total_sum = 0
        nums = [int(char) for char in str(n)]
        for num in nums:
            total_sum += num ** 2
        if total_sum in result:
            return False
        result.add(total_sum)
        n = total_sum
    return True

2. 也可以使用快慢指针来做，原理是检测该数据链是否成环。如果 n 不是快乐数，那么快指针总有一个时刻会追上慢指针。

def isHappy(self, n: int) -> bool:
    def get_next(number):
        total_sum = 0
        while number > 0:
            number, digit = divmod(number, 10)
            total_sum += digit ** 2
        return total_sum
    
    slow_runner = n
    fast_runner = get_next(n)
    while fast_runner != 1 and slow_runner != fast_runner:
        slow_runner = get_next(slow_runner)
        fast_runner = get_next(get_next(fast_runner))
    return fast_runner == 1

题目四：LeetCode 1. 两数之和

暴力解法进行遍历，时间复杂度为 O(n^2)。很自然想到可以用哈希表记录每一个 x，然后在遍历时查询哈希表中是否存在 target - x，时间复杂度降为 O(n)。注意，这里元素是 key，value 是数组元素对应的下标。

# 暴力解法
def twoSum(self, nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if (nums[i] + nums[j]) == target:
                return [i, j]
    return None

# hashtable
def twoSum(self, nums: List[int], target: int) -> List[int]:
    hashtable = dict()
    for i, num in enumerate(nums):
        if target - num in hashtable:
            return [hashtable[target - num], i]
        hashtable[num] = i
    return None