哈希表的核心“超能力”¶

核心能力：在平均情况下，以 O(1) 的时间复杂度完成插入、删除、查找操作。
本质：它提供了一种近乎即时的方式来回答“我见过这个东西吗？”或者“与这个东西关联的信息是什么？”

基于这个超能力，我们发展出了以下几种核心的算法思维模式：

模式一：空间换时间 —— “以存代查，建立备忘录”¶

这是哈希表最经典、最直接的应用。当你的算法中出现了嵌套循环，尤其是内层循环是在寻找一个“配对”或“补数”时，你就要立刻想到：我可以用哈希表替代内层循环吗？

核心思想：将一个O(n)的线性查找，降维成一个O(1)的哈希查找。
典型例题：两数之和 (Two Sum)
- 慢速思路 (O(n²))：对于每个数字 x，都向后遍历整个数组，寻找是否存在 target - x。
- 哈希表思路 (O(n))：
  1. 创建一个哈希表作为“备忘录”。
  2. 遍历数组，对于每个数字 x，不去遍历，而是直接问备忘录：“target - x 你见过吗？”
  3. 如果见过，问题解决。
  4. 如果没见过，就把当前的 x 和它的索引存入“备忘录”，以备后来的数字查询。
思维触发点：当你需要为一个元素 x 快速找到它的“另一半” y 时，就用哈希表。

模式二：分组与归类 —— “找到共同特征，进行映射”¶

当问题需要你将一系列元素按照某种“内在特征”进行分组时，哈希表是完美的工具。

核心思想：为具有相同特征的一类元素，计算出一个独一无二的、规范化的“签名”（Canonical Key），然后将这个签名作为键，将元素本身存入值（通常是一个列表）。
典型例题：字母异位词分组 (Group Anagrams)
- 内在特征：两个词互为字母异位词，意味着它们包含的字母及数量完全相同。
- “签名”计算：对字符串进行排序。"eat", "tea", "ate" 的签名都是 "aet"。
- 哈希表思路 (O(n*k log k)) (k为字符串平均长度):
  1. 创建一个 defaultdict(list) 的哈希表。
  2. 遍历每个字符串，计算它的“签名”（排序后的字符串）。
  3. 用这个签名作为键，将原字符串 append 到对应的列表中。mp["aet"].append("eat")。
思维触发点：当你需要将“看起来不同，但本质相同”的东西归为一类时，思考如何为它们定义一个统一的“身份证”（签名），并用哈希表进行归类。

模式三：快速判断存在性 —— “利用集合优化起点判断”¶

这个模式是“空间换时间”的延伸，但更侧重于利用哈希集合（Set，可以看作只有键的哈希表）来优化逻辑，避免重复计算。

核心思想：先将所有元素放入一个哈希集合，然后利用其O(1)的查询特性，来判断一个元素是否满足某种“特殊条件”（例如，是否是序列的起点），从而避免大量不必要的计算。
典型例题：最长连续序列 (Longest Consecutive Sequence)
- 朴素思路 (O(n log n))：先排序，再遍历。简单直观，但排序本身耗时。
- 哈希表思路 (O(n))：
  1. 将所有数字放入一个哈希集合 num_set。目的：为了能 O(1) 地回答“数字 k 是否存在？”
  2. 遍历每个数字 num，进行一个关键判断：if num - 1 not in num_set:。
  3. 这个判断的目的：只对一个连续序列的最小的那个数（起点）进行处理。对于 [1,2,3,4]，我们只对 1 进行详细的向后查找，而 2,3,4 都会因为 num-1 存在而被跳过。
  4. 这极大地减少了计算量，将一个看似O(n²)的嵌套循环，通过均摊分析，变为了O(n)。
思维触发点：当你的算法需要处理连续、相邻的元素关系，并且可能存在大量重复计算时，思考能否用哈希集合来快速判断“前驱”或“后继”是否存在，从而找到一个唯一的“起点”来开始计算。

总结：你的哈希表工具箱¶

下次遇到算法题，尤其是关于数组或字符串的，可以从以下几个角度思考哈希表能否帮你优化：

当你遇到...	你可以思考...	哈希表的作用
嵌套循环，尤其是内层在查找	能否用“备忘录”替代内层循环？	空间换时间，O(n)查找 -> O(1)查找
需要分组的问题	能否为每一组定义一个唯一的“签名”作为键？	分组与归类，`map[签名].append(元素)`
涉及大量“是否存在”的判断	能否先把数据存入哈希集合？	快速判断存在性，`if x in my_set:`
处理序列/连续性问题	能否用哈希集合判断元素的“前驱”是否存在，从而找到起点？	优化起点判断，`if x-1 not in my_set:`

1两数之和¶

给定一个数组找出两个数和为目标值target的数组下标

In [ ]:

Copied!





"""类名 (Class Name): 应使用大驼峰命名法 (PascalCase)
函数/方法名 (Function/Method Name): 应使用蛇形命名法 (snake_case)，即所有字母小写并用下划线分隔"""
class Solution:
    def sum_two(self, target, nums):
        """哈希表（词典）能直接查询某个元素，相比于列表的挨个遍历"""
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target-num], i]
            hashtable[num] = i
        return []

test_nums = [1, 2, 5, 10]
target = 11
sumtwo = Solution()
a = sumtwo.sum_two(target, test_nums)
print(a)
"""类名 (Class Name): 应使用大驼峰命名法 (PascalCase)
函数/方法名 (Function/Method Name): 应使用蛇形命名法 (snake_case)，即所有字母小写并用下划线分隔"""
class Solution:
    def sum_two(self, target, nums):
        """哈希表（词典）能直接查询某个元素，相比于列表的挨个遍历"""
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target-num], i]
            hashtable[num] = i
        return []

test_nums = [1, 2, 5, 10]
target = 11
sumtwo = Solution()
a = sumtwo.sum_two(target, test_nums)
print(a)

49字母异或位分组¶

给定一个数组，将字母异位词组合在一起输出

In [ ]:

Copied!





import collections
from typing import List

class Solution:
    """
    该类用于将字母异位词组合在一起。
    """
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

        # 创建一个默认值为列表的字典,相比于dict，能直接加入不存在的键
        mp = collections.defaultdict(list)

        # 遍历输入列表中的每个字符串
        for st in strs:
            # 将字符串排序后作为键
            key = "".join(sorted(st))
            print(f"原来字符串为{st}\n sorted(st)后的字符串为{sorted(st)}\n key值为{key}")
            """
            sorted() 函数的返回值永远是一个列表,['a', 'e', 't']
            .join()将一个可迭代对象中的所有元素连接成一个单一的字符串
            空字符串 ""，引号中的字符表示在连接处加入相应的字符，这里表示无缝连接
            """
            # 将原字符串添加到对应键的列表中
            mp[key].append(st)
        
        # 返回字典中所有的值（即分组后的列表）
        return list(mp.values())

# --- 以下是调用函数的示例 ---

# 1. 创建一个Solution类的实例
solver = Solution()

# 2. 准备一组用于测试的字符串列表
input_strings = ["eat", "tea", "tan", "ate", "nat", "bat"]

# 3. 调用实例的 groupAnagrams 方法，并传入测试数据
result = solver.groupAnagrams(input_strings)

# 4. 打印输入和输出结果
print(f"输入 (Input): {input_strings}")
print(f"输出 (Output): {result}")
import collections
from typing import List

class Solution:
    """
    该类用于将字母异位词组合在一起。
    """
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

        # 创建一个默认值为列表的字典,相比于dict，能直接加入不存在的键
        mp = collections.defaultdict(list)

        # 遍历输入列表中的每个字符串
        for st in strs:
            # 将字符串排序后作为键
            key = "".join(sorted(st))
            print(f"原来字符串为{st}\n sorted(st)后的字符串为{sorted(st)}\n key值为{key}")
            """
            sorted() 函数的返回值永远是一个列表,['a', 'e', 't']
            .join()将一个可迭代对象中的所有元素连接成一个单一的字符串
            空字符串 ""，引号中的字符表示在连接处加入相应的字符，这里表示无缝连接
            """
            # 将原字符串添加到对应键的列表中
            mp[key].append(st)
        
        # 返回字典中所有的值（即分组后的列表）
        return list(mp.values())

# --- 以下是调用函数的示例 ---

# 1. 创建一个Solution类的实例
solver = Solution()

# 2. 准备一组用于测试的字符串列表
input_strings = ["eat", "tea", "tan", "ate", "nat", "bat"]

# 3. 调用实例的 groupAnagrams 方法，并传入测试数据
result = solver.groupAnagrams(input_strings)

# 4. 打印输入和输出结果
print(f"输入 (Input): {input_strings}")
print(f"输出 (Output): {result}")

In [ ]:

Copied!





class Solution:
    def test(self, strs):
        hashdict = collections.defaultdict(list)
        for i in strs:
            key = ''.join(sorted(i))
            hashdict[key].append(i)
        return list(hashdict.values())
strs = ['aet', 'ate', 'eat', 'app', 'ppa']
jw = Solution()
a = jw.test(strs)
print(a)
class Solution:
    def test(self, strs):
        hashdict = collections.defaultdict(list)
        for i in strs:
            key = ''.join(sorted(i))
            hashdict[key].append(i)
        return list(hashdict.values())
strs = ['aet', 'ate', 'eat', 'app', 'ppa']
jw = Solution()
a = jw.test(strs)
print(a)

128最长连续序列¶

给定一个数组，找到连续的最长序列长度

核心思路

凡是可以查找的，都用哈希表

1.确定起点(通过-1在哈希表查找确定起点)

2.通过不断+1查找，确定长度

In [4]:

Copied!





class Solution:
    """
    (1)确定连续序列的起点
    (2)确定该序列的最大长度
    """
    def longestConsecutive(self, nums: List[int]) -> int:
        max_length = 0
        nums_set = set(nums)
        for i in nums_set:
            if i-1 not in nums_set:
                cur_num = i
                cur_length = 1
                while cur_num + 1 in nums_set:
                    cur_length += 1
                    cur_num += 1
                max_length = max(max_length, cur_length)
                
        return max_length
        # --- 示例调用 ---
solver = Solution()
test_nums = [100, 4, 200, 1, 3, 2]
print(f"输入: {test_nums}, 最长连续序列长度: {solver.longestConsecutive(test_nums)}") # 应为 4 (1,2,3,4)

test_nums_with_duplicates = [1, 2, 0, 1]
print(f"输入: {test_nums_with_duplicates}, 最长连续序列长度: {solver.longestConsecutive(test_nums_with_duplicates)}") # 应为 3 (0,1,2)
class Solution:
    """
    (1)确定连续序列的起点
    (2)确定该序列的最大长度
    """
    def longestConsecutive(self, nums: List[int]) -> int:
        max_length = 0
        nums_set = set(nums)
        for i in nums_set:
            if i-1 not in nums_set:
                cur_num = i
                cur_length = 1
                while cur_num + 1 in nums_set:
                    cur_length += 1
                    cur_num += 1
                max_length = max(max_length, cur_length)
                
        return max_length
        # --- 示例调用 ---
solver = Solution()
test_nums = [100, 4, 200, 1, 3, 2]
print(f"输入: {test_nums}, 最长连续序列长度: {solver.longestConsecutive(test_nums)}") # 应为 4 (1,2,3,4)

test_nums_with_duplicates = [1, 2, 0, 1]
print(f"输入: {test_nums_with_duplicates}, 最长连续序列长度: {solver.longestConsecutive(test_nums_with_duplicates)}") # 应为 3 (0,1,2)

输入: [100, 4, 200, 1, 3, 2], 最长连续序列长度: 4
输入: [1, 2, 0, 1], 最长连续序列长度: 3

In [ ]:

Copied!





class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        max_len = 0
        hashset = set(nums)
        for i in hashset:
            if i - 1 not in hashset:
                cur_len = 1
                cur_start = i
                while cur_start + 1 in hashset:
                    cur_start += 1
                    cur_len += 1
                max_len = max(max_len, cur_len)
                
        return max_len
nums = [1, 100, 3, 10, 2]
jw = Solution()
max_len = jw.longestConsecutive(nums)
max_len
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        max_len = 0
        hashset = set(nums)
        for i in hashset:
            if i - 1 not in hashset:
                cur_len = 1
                cur_start = i
                while cur_start + 1 in hashset:
                    cur_start += 1
                    cur_len += 1
                max_len = max(max_len, cur_len)
                
        return max_len
nums = [1, 100, 3, 10, 2]
jw = Solution()
max_len = jw.longestConsecutive(nums)
max_len