441_数组与哈希表面试题¶

def two_sum(nums, target):
    """
    暴力法 O(n²)，哈希法 O(n)
    思路：遍历时用哈希表记录"之前见过的数"，
    对当前数 num，查哈希表里有没有 target-num
    """
    seen = {}                              # 哈希表：{数值: 下标}

    for i, num in enumerate(nums):
        complement = target - num          # 需要的另一个数

        if complement in seen:             # 在之前见过的数里找到了
            return [seen[complement], i]   # 返回两个下标

        seen[num] = i                      # 记录当前数和它的下标

    return []                              # 没有找到（题目保证有解）

# 测试
print(two_sum([2, 7, 11, 15], 9))   # [0, 1]（2+7=9）
print(two_sum([3, 2, 4], 6))        # [1, 2]（2+4=6）
print(two_sum([3, 3], 6))           # [0, 1]（3+3=6）

from collections import defaultdict

def group_anagrams(strs):
    """
    思路：字母异位词排序后一定相同（'eat' 和 'tea' 排序后都是 'aet'）
    用排序结果作哈希表的键，相同键的词分到一组
    """
    groups = defaultdict(list)             # 默认值是空列表

    for word in strs:
        key = ''.join(sorted(word))        # 排序作为键：'eat'→'aet'
        groups[key].append(word)           # 加入对应分组

    return list(groups.values())           # 返回所有分组

# 测试
words = ["eat", "tea", "tan", "ate", "nat", "bat"]
result = group_anagrams(words)
print(result)
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

def group_anagrams_v2(strs):
    groups = defaultdict(list)
    for word in strs:
        count = [0] * 26                   # 26个字母的计数
        for c in word:
            count[ord(c) - ord('a')] += 1  # 统计每个字母出现次数
        key = tuple(count)                 # 用计数元组作键（可哈希）
        groups[key].append(word)
    return list(groups.values())

def longest_consecutive(nums):
    """
    思路：用集合存所有数字，对每个序列的起点（num-1不在集合中）
    开始向后数，统计序列长度
    """
    num_set = set(nums)                    # 转成集合，O(1)查找
    max_len = 0

    for num in num_set:
        if num - 1 not in num_set:         # 只从序列起点开始数
            current = num
            length = 1

            while current + 1 in num_set:  # 向后延伸
                current += 1
                length += 1

            max_len = max(max_len, length)

    return max_len

# 测试
print(longest_consecutive([100, 4, 200, 1, 3, 2]))  # 4（1,2,3,4）
print(longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))  # 9

# 哈希表常用操作
d = {}
d[key] = value          # 插入/更新
value = d.get(key, 0)   # 安全取值，不存在返回0
key in d                # 判断存在，O(1)

# defaultdict 自动初始化
from collections import defaultdict
d = defaultdict(int)    # 默认值0
d = defaultdict(list)   # 默认值[]
d = defaultdict(set)    # 默认值set()

# Counter 计频
from collections import Counter
freq = Counter([1,1,2,3,3,3])  # {3:3, 1:2, 2:1}
freq.most_common(2)             # [(3,3), (1,2)] 最常见的2个

# 集合操作
s = set(nums)           # 去重
x in s                  # O(1)查找
s1 & s2                 # 交集
s1 | s2                 # 并集
s1 - s2                 # 差集