LeetCode 哈希表专题
从快速查找到原地映射

01LeetCode 1两数之和

简单 ｜ 核心知识点：补数查找 · 值到下标 · 先查后存

题意与约束

给定整数数组 nums 和 target，返回两个不同下标，使对应数之和为 target。题目保证恰好一个有效答案，返回顺序任意。允许负数、0 和重复值；数组长度至少为 2。

解法一 · 暴力枚举，建立正确基线

枚举所有下标对 i < j。j 从 i+1 开始，同时避免重复配对与使用自身。只要发现和等于 target 就返回；遍历穷尽了所有合法下标对，因此不会漏解。

from typing import List

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]
        return []

关键代码解释：range(i + 1, len(nums)) 保证 i ≠ j。最后的空列表是防御性返回，在本题保证有解的有效输入中不会执行。

最坏比较 n(n−1)/2 对，只使用常数个变量；返回的两个下标占 O(1) 空间。

解法二 · 一遍哈希表（推荐）

1. 建立 seen[value] = index，只保存当前下标左侧的元素。
2. 读到 x 时，先计算补数 need = target - x。若 need 已存在，返回它的旧下标与当前下标。
3. 没有匹配才执行 seen[x] = i，供后续元素查询。

正确性不变量：处理下标 i 之前，seen 中只包含下标小于 i 的值及其某个下标。如果答案为 (a,b) 且 a<b，处理 b 时 a 的值已经在表中，所以一定能找到；先查后存保证两个下标不同。相同值覆盖旧下标仍保留一个合法的历史位置。

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for i, x in enumerate(nums):
            need = target - x
            if need in seen:
                return [seen[need], i]
            seen[x] = i
        return []

关键代码解释：need in seen 查询的是值构成的键；seen[need] 取出下标。查询必须在写入当前元素之前。下标 0 是合法答案，不能写成 if seen.get(need)。

示例推演

nums=[2,7,11,15]，target=9。

最多一次遍历，哈希表最坏保存 O(n) 个不同值；不修改输入。

易错点与边界检查

• 返回下标而非数值；不要先排序丢掉原下标。
• 先写后查会让 [3,3] 的第一个 3 匹配自身，产生 [0,0]。
• [0,4,3,0]、target=0 → [0,3]；[-3,4,3,90]、target=0 → [0,2]。
• [3,2,4]、target=6 → [1,2]；长度为 2 也要正确处理。

02LeetCode 136只出现一次的数字

简单 ｜ 核心知识点：频次统计 · 异或 · 成对消去

题意与约束

非空整数数组中，恰好一个数字出现一次，其他每个数字都出现两次，返回唯一的单次数字。原题要求线性时间和常数额外空间。

解法一 · 哈希计数（理解用的基线）

先扫描数组累加每个值的次数，再扫描频次表找到次数为 1 的键。表里准确保存了每个值的出现次数，唯一满足条件的键就是答案。这套模型也适用于「找出现 t 次的值」，但额外空间不满足本题要求。

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        freq = {}
        for x in nums:
            freq[x] = freq.get(x, 0) + 1
        for x, count in freq.items():
            if count == 1:
                return x
        raise ValueError("题目保证恰有一个单次元素")

关键代码解释：get(x, 0) 让首次出现的值从 0 开始计数；items() 同时提供值和频次。异常仅表示违反题目约束的输入。

两轮分别遍历 n 个元素和 u 个键。该版本可作为正确性对照，不能作为满足常数空间要求的最终方案。

解法二 · 异或消去（满足原题要求）

异或 ^ 按二进制位运算：位相同得到 0，位不同得到 1。它满足交换律与结合律。把全部数字异或后，每一对相同数字都会消成 0，只留下单次数字。

正确性不变量：每轮结束后 ans 等于已处理前缀的全部元素的异或。最终将相同数字按交换律配对，每对贡献 0，因此结果恰为唯一单次数字。初始化为 0 是因为 0 是异或的单位元。

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for x in nums:
            ans ^= x
        return ans

关键代码解释：ans ^= x 等价于 ans = ans ^ x。这里的 ^ 不是幂运算，Python 的幂是 **；对题目范围内的负整数同样可以消去。

示例推演

nums=[4,1,2,1,2]，计数结果为 {4:1,1:2,2:2}。

只遍历一次并保存一个异或累积值；固定范围整数的位运算视为 O(1)。不修改输入。

易错点与边界检查

• 不能把异或解法直接用于「其他元素均出现三次」或「有两个单次元素」；消去条件已经改变。
• 不要用 sum(set(nums)) * 2 - sum(nums) 冒充常数空间，集合仍占 O(n)。
• [1] → 1；[2,2,1] → 1；[-1,2,2] → -1；[0,5,5] → 0。
• 空数组不是有效输入；有多个单次元素时，异或结果也未必属于原数组。

03LeetCode 169多数元素

简单 ｜ 核心知识点：频次阈值 · 摩尔投票 · 相异配对消去

题意与约束

返回非空数组中出现次数严格大于 ⌊n/2⌋ 的元素。题目保证它一定存在，因此结果唯一。进阶要求 O(n) 时间、O(1) 额外空间。

解法一 · 频次表与阈值

一边累加次数，一边判断是否超过 n//2。某个频次一旦超过阈值，后面再读多少元素都不会改变整个数组长度和该元素已出现的次数，因此可以提前返回。

from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        freq = {}
        threshold = len(nums) // 2
        for x in nums:
            freq[x] = freq.get(x, 0) + 1
            if freq[x] > threshold:
                return x
        raise ValueError("题目保证多数元素存在")

关键代码解释：> threshold 必须严格大于；>= 会把出现一半的元素当成多数元素。n=1 时阈值为 0，第一轮即可返回。

频次表扫描最多 n 次，保存最多 u 个键。满足普通要求，但未满足进阶常数空间要求。

解法二 · Boyer–Moore 摩尔投票（推荐）

1. 维护候选人 candidate 和票数 votes。
2. votes 为 0 时，把当前元素设为新的候选人。
3. 当前元素与候选人相同就加票，否则减票。
4. 遍历结束后，返回候选人。

为什么成立：把不同的两个值成对删除。若删除对包含多数元素，则多数元素数量和其他元素总数量同时减一，其数量优势保持；若两个都不是多数元素，优势反而扩大。因此多数元素无法被全部抵消。候选人与票数表示当前前缀在抵消后保留的若干个相同值；结合题目保证，最终候选人一定是多数元素。

from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = nums[0]
        votes = 0
        for x in nums:
            if votes == 0:
                candidate = x
            if x == candidate:
                votes += 1
            else:
                votes -= 1
        return candidate

关键代码解释：两个 if 有不同职责：第一个选候选人，第二个给当前元素记票；如果随意改成 elif，新候选人的第一票可能丢失。votes 是「抵消后的净票数」，不是 candidate 在原数组中的出现次数。

示例推演

nums=[2,2,1,1,1,2,2]，计数法最终得 2 出现 4 次、1 出现 3 次，4>7//2。

只维护 candidate 与 votes；不修改输入。

易错点与边界检查

• 多数元素不等于一般的「出现最多」：出现最多也可能没超过一半。
• votes 归零当轮仍已处理完当前元素，下一轮再选择新的候选人。
• [3,2,3] → 3；[7] → 7；[-1,-1,2] → -1；全相同数组直接返回该值。
• 排序后取中位数也能利用多数性质，但 O(n log n) 时间，Python 排序还可能有 O(n) 辅助空间，因此这里优先掌握计数与投票。

04LeetCode 49字母异位词分组

中等 ｜ 核心知识点：规范化键 · 等价类分桶 · 字符频次元组

题意与约束

将字符串数组中的字母异位词放入同一组。异位词的每个字符及其出现次数都相同，仅排列顺序可以不同。输入仅含小写英文字母，允许空字符串与重复字符串。组之间、组内顺序均可任意。

解法一 · 排序后的字符串作为规范键

每个字符串排序后得到唯一规范形式。若两个字符串互为异位词，它们排序后相同；反之，排序后相同就说明各字母的频次相同。因此以规范形式作键，把原字符串追加到同一桶即可。

from typing import List
from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for s in strs:
            key = "".join(sorted(s))
            groups[key].append(s)
        return list(groups.values())

关键代码解释：sorted(s) 返回字符列表，用 "".join(...) 转回可哈希字符串；桶里放原始 s，而不是排序后的 key。list(groups.values()) 返回具体嵌套列表，不能直接返回字典视图。

更精确时间为 O(n + Σᵢ |sᵢ| log(|sᵢ|+1))，包含建键与哈希成本。最多 g 个长度不超过 k 的键，临时排序列表 O(k)；输出桶保存 n 个原字符串引用、g 个列表，不复制原字符串字符。常见把输出合计的上界写作 O(nk+n)。

解法二 · 26 位计数元组作为规范键（固定字母表优化）

对每个字符串创建长度 26 的频次数组，第 j 项表示字母 chr(ord('a')+j) 出现几次。转成元组后可用作字典键，频次向量完全相同的字符串必为异位词。与排序相比，它直接保存了判断异位词所需要的信息。

from typing import List
from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for s in strs:
            count = [0] * 26
            for ch in s:
                count[ord(ch) - ord('a')] += 1
            key = tuple(count)
            groups[key].append(s)
        return list(groups.values())

关键代码解释：ord(ch) - ord('a') 把 a…z 映射到 0…25；每个字符串必须新建 count；tuple(count) 生成不可变键。不能将 count 直接当键，也不能仅用字符集合当键，因为集合丢失重复次数。

示例推演

strs=["eat","tea","tan","ate","nat","bat"]，下面省略计数向量中的 0 项。

一种合法输出：[["eat","tea","ate"],["tan","nat"],["bat"]]。它与原题示例顺序不同，但分组关系相同。

更精确时间为 O(nΣ + Σᵢ |sᵢ|)，即 O(n+总字符数)，空字符串也有建键成本。Σ 固定时键长度是常数，辅助空间 O(g)，加输出总体 O(n)。不应直接写成 O(nk) 而忽略 k=0 的情况。

易错点与边界检查

• [""] → [[""]]：空串对应空排序键或全零计数元组，不能跳过。
• ["a","a"] → [["a","a"]]：需要保留重复字符串，不能用 set 收集桶。
• ["ab","aab"] 必须分两组；仅排序去重后的字符、字符总和或字符集合都可能误分组。
• 返回结果无需排序。测试时应比较规范化后的分组，不能仅比较列表顺序。
• 若字符范围变成 Unicode，26 位数组就不再适用，需重新设计键。

05LeetCode 128最长连续序列

中等 ｜ 核心知识点：集合去重 · 起点判定 · 总访问次数分析

题意与约束

在未排序整数数组中找出最长的数值连续序列长度。数值相差 1 才算连续，不要求在原数组中相邻。重复值不增加长度，空数组返回 0。原题要求 O(n) 时间。

解法一 · 排序后扫描（理解用的基线）

排序让相邻数值相聚。扫描时：相等就跳过，恰好加一就延长，否则开始新序列。current 始终是以当前不同值结尾的连续段长度，best 保存所有已看到段的最大长度，因此扫描结束得到最长长度。

from typing import List

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        arr = sorted(nums)
        best = current = 1
        for i in range(1, len(arr)):
            if arr[i] == arr[i - 1]:
                continue
            if arr[i] == arr[i - 1] + 1:
                current += 1
            else:
                current = 1
            best = max(best, current)
        return best

关键代码解释：相等时直接 continue，既不增加也不重置 current。新段必须从 1 开始，因为当前数自身就是一个长度为 1 的连续段。

sorted(nums) 创建新数组；Python 的排序也可需要 O(n) 辅助空间。保留输入但不满足原题的线性时间要求。即便换成 nums.sort() 也不能直接声称 Python 排序只用 O(1) 空间。

解法二 · 集合 + 只从起点扩展（推荐）

1. 先建立集合 values，去掉重复值并支持快速查找。
2. 遍历集合中的每个 x：若 x−1 存在，x 就不是这一段的起点，直接跳过。
3. 只有 x−1 不存在才从 x 开始不断查找 x+1、x+2…，直到某个值缺失。
4. 用 end - x 更新最长长度，end 是第一个不在集合中的数。

正确性：集合被划分为若干个互不相交的最大连续段，每段都有唯一的最小值。起点判断恰好选择这个最小值，向右扩展恰好覆盖该段，取最大即为答案。

from typing import List

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        values = set(nums)
        best = 0
        for x in values:
            if x - 1 in values:
                continue
            end = x
            while end in values:
                end += 1
            best = max(best, end - x)
        return best

关键代码解释：外层必须遍历去重后的 values。if x - 1 in values: continue 是保证线性复杂度的核心。end 退出时位于段尾后一位，因此段长为 end−x，不再加 1。

示例推演

nums=[100,4,200,1,3,2]。集合无序，下面按数值顺序展示逻辑检查，程序不依赖遍历顺序。

为什么 while 嵌套在 for 里仍然是线性？

外层做 u 次起点检查。内层只有各段起点会执行；不同段互不重叠，所以内层成功查询总共 u 次，每段再有一次失败查询，最多 u 次。加上建集合扫描 n 个元素，总查询次数 O(n+u)，因此平均 O(n)。不能只按缩进层数判断复杂度。

每个不同值只属于一段且只被成功扩展一次；不修改输入。极端哈希碰撞可能让整体退化。

易错点与边界检查

• 连续序列按数值而非原位置判断；它不是最长连续子数组，也不是最长递增子序列。
• 若从每个数都向右扩展，[1,2,…,n] 会重复扫描成 O(n²)。
• 即使判断起点，外层遍历原数组也可能反复扩展重复的起点。例如许多个 1 加上 [2,3,…,m]，仍可退化到 O(n²)。
• [] → 0；[1,1,1] → 1；[1,0,1,2] → 3；[-2,-1,0,2] → 3。
• [0,3,7,2,5,8,4,6,0,1] → 9；集合遍历期间不必删除或添加元素。

06LeetCode 41缺失的第一个正数

困难 ｜ 核心知识点：答案范围证明 · 原地置换 · 符号标记

题意与约束

返回未排序整数数组中缺失的最小正整数。数组可能有负数、0、重复值和很大的正数，题目要求 O(n) 时间、O(1) 额外空间。原题数组非空，下面代码也能处理空数组并返回 1。

先证明答案范围：为什么只关心 1…n？

长度 n 的数组最多覆盖 n 个不同正整数。若 1…n 全部出现，答案就是 n+1；若其中有缺失，最小缺失值就在 1…n。因此答案一定属于 [1,n+1]，非正数和大于 n 的值都不影响 1…n 是否齐全。

解法一 · 集合查询（空间换时间的基线）

把所有值放入集合，从 1 到 n+1 依次查询，遇到第一个不在集合中的值就返回。按递增顺序查询保证返回的是最小正缺失值。范围证明保证循环一定会返回。

from typing import List

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        values = set(nums)
        for x in range(1, len(nums) + 2):
            if x not in values:
                return x
        return len(nums) + 1

关键代码解释：range(1, len(nums) + 2) 包含 n+1；末尾 return 只是防御性兜底，按范围证明不会执行。集合不需要保留次数。

建集合与查询均平均线性；不修改输入，但不满足本题常数额外空间要求。

解法二 · 原地置换 / 把值送回家（推荐）

规定位置 i 应当存放 i+1。遍历数组时，如果当前值 x 在 [1,n] 且它的目标位置 x−1 没有 x，就交换过去。交换后当前位置拿到了新值，必须继续用 while 处理，直到当前值不合法或已在合适位置。最后从左到右扫描，首个 nums[i] ≠ i+1 的位置对应答案 i+1。

正确性：一次有效交换会把一个范围内的值 x 放到它的唯一目标格 x−1；后续交换不会把已正确的值赶走，因为发起相同目标的交换会被「目标格已有 x」条件阻止。遍历结束后，每个存在的合法值都在它的目标格中。因此第一个不匹配位置就代表最小缺失正整数。

from typing import List

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n:
                target = nums[i] - 1
                if nums[target] == nums[i]:
                    break
                nums[i], nums[target] = nums[target], nums[i]
        for i, x in enumerate(nums):
            if x != i + 1:
                return i + 1
        return n + 1

关键代码解释：target = nums[i] - 1 在交换前缓存目标下标，避免多重赋值时重新读取被改动的 nums[i]。先检查范围才可访问目标格，避免负下标和越界。nums[target] == nums[i] 同时处理已归位和重复值，不满足就交换。

示例推演 · nums=[3,4,-1,1]

为什么多次交换仍是 O(n)？

每次交换至少新增一个正确位置，且已经正确的位置不会被破坏。正确位置最多 n 个，所以所有 while 的交换次数总共不超过 n。外层、最终扫描各 O(n)，总体 O(n)，并非每个 i 都交换 n 次。

不使用哈希容器，只维护下标和常数变量；会修改 nums。为了保留原数组而传入 nums[:] 会额外占 O(n) 空间，不能算入原题常数空间解法。

解法三 · 符号标记 / 把格子当存在位

1. 把所有不在 [1,n] 的数替换为 n+1，使整个数组先变成正数，清除原有负号的干扰。
2. 再次扫描，对每个绝对值 x，如果 1≤x≤n，就把位置 x−1 的数置为负数，表示 x 存在。
3. 最后第一个仍为正数的位置 i，表示 i+1 没出现；全部为负则返回 n+1。

正确性不变量：标记阶段处理完一段前缀后，凡前缀里出现过的合法绝对值 x，其对应格子均为负。标记只改变符号，不改变绝对值，因此后续读取仍能恢复待处理的原值；清洗出的 n+1 不会误标记任何合法格。

from typing import List

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            if nums[i] <= 0 or nums[i] > n:
                nums[i] = n + 1
        for i in range(n):
            x = abs(nums[i])
            if 1 <= x <= n:
                nums[x - 1] = -abs(nums[x - 1])
        for i, x in enumerate(nums):
            if x > 0:
                return i + 1
        return n + 1

关键代码解释：读取时用 abs(nums[i])，因为该格可能已被前面的数打上负号；写标记用 -abs(...)，不能简单乘 −1，否则重复值会把负号翻回正号。清洗阶段不能用 0 作占位，因为负 0 仍是 0，无法承载存在位。

符号标记推演 · 同一输入 [3,4,-1,1]

三轮线性扫描；每轮执行常数工作；修改原数组。与原地置换相比无需嵌套 while，但要严格区分清洗、标记、读取三个阶段。

易错点与边界检查

• 必须用 while 而非仅交换一次：一个位置可能连续收到多个需要送走的新值。
• 原地置换必须防重复。[1,1] 若无目标格检查，会一直交换相同值。
• 值 x 对应下标 x−1，最后缺失位置 i 对应值 i+1，不能混淆。
• [1,2,0] → 3；[7,8,9,11,12] → 1；[1,1] → 2；[2] → 1；[1] → 2。
• [-1,-2] → 1；[1,2,3] → 4；[3,4,-1,1] → 2；防御性空输入 [] → 1。
• 符号标记应在清洗后进行；原有负数不代表某个正数已经出现。