一次吃透LeetCode哈希表经典题：附完整思路与代码解析

哈希表核心知识点整理

1. 哈希表是什么？

本质定义：一种存储数据的容器，核心是通过「哈希函数」将数据映射到特定的存储位置，实现快速访问。

核心原理：输入数据（如 int 型数字 5） → 哈希函数 → 映射为数组下标 → 存入对应位置

2. 哈希表有什么用？

核心优势是极致高效的查找性能：

时间复杂度： 平均查找时间：O(1)（常数级，单次访问就能定位数据）

空间复杂度：O(n)（需要额外的空间存储映射关系）

对比其他查找方式：

3. 什么时候用哈希表？

核心场景：频繁查找某个元素的时候，比如：统计数据出现的次数（如字符串中字符频率、数组中数字出现次数），判断元素是否存在（如两数之和、数组去重），快速映射键值对（如字典/映射表场景）

4. 怎么用哈希表？（两种基础实现方式）

方式1：通用哈希表（键值对结构）

形式：<index, n[index]>，即「键（key）→ 值（value）」的映射

用途：适合数据范围不固定、需要自定义映射关系的场景（如 Python 的 dict、Java 的 HashMap）

方式2：用数组模拟简易哈希表

适用场景：数据范围很小且已知，比如：

统计字符串中的字符（范围：a-z/A-Z，共 26/52 个）

整数范围有限（如 1~1000、-1000~1000）

实现步骤：

1） 定义数组作为存储容器，长度覆盖数据范围（如 [-1000,1000] 可定义长度为 2001 的数组，通过偏移量 x + 1000 将负数转为非负下标）

2） 数据存入：count[index] += 1（统计次数）或直接赋值

3） 数据查找：直接访问 count[index]，O(1) 时间获取结果

补充：关键细节与避坑点

1） 哈希冲突：不同数据经过哈希函数计算后，映射到同一个位置的情况。实际应用中需要解决（如链地址法、开放地址法）。

2） 简易哈希表的局限性：仅适用于数据范围小的场景，数据范围过大时会造成空间浪费（如存储 1~10^9 的数据，数组长度需要 10^9，内存无法承受）。

3） 偏移量的使用：处理负数数据时，需要通过偏移量将数据转为非负下标，避免数组越界。

题目1：两数之和（LeetCode 1）

1. 题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

• 示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9，返回 [0, 1]。

• 示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

2. 暴力解法

思路拆解

1） 先固定其中一个数：遍历数组，依次把每个元素nums[i]作为第一个数。

2） 依次与该数之前的数相加：在nums[i]之前的元素（下标j < i）中，逐个判断nums[i] + nums[j]是否等于目标值target。如果相等，直接返回[j, i]；如果不相等，继续遍历下一个数。

对应代码（C++示例）

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int n = nums.size(); // 固定一个数nums[i] for (int i = 0; i < n; ++i) { // 与该数之前的数相加 for (int j = 0; j < i; ++j) { if (nums[i] + nums[j] == target) { return {j, i}; } } } return {}; // 题目保证有解，此行仅为语法兼容 } };

复杂度分析

时间复杂度：O(n^2)，两层嵌套循环，最坏情况需要遍历所有元素组合。

空间复杂度：O(1)，仅用常数额外空间。

3. 哈希表解法详解

核心算法思路

基础逻辑：把「数组元素值」和「它的下标」绑定存入哈希表，然后遍历数组时，直接在哈希表中查找 target - nums[i]，如果存在，就说明找到了两个数，返回它们的下标。

优化技巧（关键！）：不需要先把所有元素都放进哈希表再遍历一次（会有重复元素处理问题），而是边遍历边存哈希表：

1. 对当前元素 nums[i]，计算目标补数 x = target - nums[i]

2. 检查哈希表中是否已经存在 x：

如果存在：说明 x 是之前遍历过的元素，直接返回 {hash[x], i}（hash[x] 是 x 的下标，i 是当前元素的下标）

如果不存在：把当前元素 nums[i] 和它的下标 i 存入哈希表，继续遍历

复杂度分析：

时间复杂度：O(N)，遍历数组一次，哈希表的查询和插入都是 O(1) 平均时间

空间复杂度：O(N)，最坏情况下哈希表需要存储所有元素

本质是用空间换时间，比暴力解法的 O(N^2) 时间复杂度更优

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> hash; // <nums[i], i> 键值对：元素值 -> 下标 for(int i = 0; i < nums.size(); i++) { int x = target - nums[i]; // 计算当前元素的补数 if(hash.count(x)) // 检查补数是否已经存在于哈希表中 return {hash[x], i}; // 存在则直接返回结果 hash[nums[i]] = i; // 不存在则将当前元素存入哈希表 } // 照顾编译器，虽然题目保证有解，但语法上需要return return {-1, -1}; } };

4. 关键知识点拆解

1） 哈希表（unordered_map）的核心用法

定义：unordered_map<int, int> hash;

第一个模板参数 int：键的类型（这里存数组元素的值）

第二个模板参数 int：值的类型（这里存数组元素的下标）

常用操作：

hash.count(x)：检查哈希表中是否存在键为 x 的元素，存在返回 1，不存在返回 0，时间复杂度 O(1)
hash[x] = i：将键为 x、值为 i 的键值对存入哈希表

hash[x]：访问键为 x 对应的值（如果不存在会自动插入默认值，所以查询时优先用 count）

2） 边遍历边存的核心优势

避免了二次遍历，直接一次遍历完成查询和存储

完美处理重复元素的情况：比如 nums = [3,3]，target = 6：遍历第一个 3 -> 补数是 3，哈希表中不存在，存入 hash[3] = 0；遍历第二个 3 -> 补数是 3，哈希表中存在 hash[3] = 0，直接返回 [0,1]

不会出现同一个元素被重复使用的情况：因为当前元素还没存入哈希表，查询时只会匹配之前遍历过的元素

3） 易错点与细节

题目保证有解，所以循环结束前一定会 return，最后的 return {-1, -1} 只是为了满足C++的语法检查，实际不会执行

返回的下标顺序：可以是 {hash[x], i}，也可以是 {i, hash[x]}，题目不要求顺序

哈希表的键是数组元素的值，值是数组下标，不要搞反！如果键存下标、值存元素值，就无法通过值快速查询下标了

题目2：判定是否互为字符重排LeetCodeLe（LeetCode 面试题 01.02）

1. 题目描述

给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

• 示例 1：
输入：s1 = "abc", s2 = "bca"
输出：true

• 示例 2：
输入：s1 = "abc", s2 = "bad"
输出：false

2. 两个哈希表解法

两个哈希表的实现逻辑是：

1） 先判断两个字符串长度是否相等，不等直接返回false

2） 分别用两个哈希表统计s1和s2中每个字符的出现次数

3） 遍历其中一个哈希表，检查两个表中每个字符的频次是否完全一致

#include <string> #include <unordered_map> using namespace std; class Solution { public: bool CheckPermutation(string s1, string s2) { // 1. 长度不等，直接返回false if (s1.size() != s2.size()) { return false; } // 2. 定义两个哈希表，分别统计两个字符串的字符频次 unordered_map<char, int> map1, map2; // 统计s1的字符频次 for (char ch : s1) { map1[ch]++; } // 统计s2的字符频次 for (char ch : s2) { map2[ch]++; } // 3. 遍历map1，对比两个哈希表的频次 for (auto& pair : map1) { char ch = pair.first; int count = pair.second; // 如果map2中不存在该字符，或频次不相等，直接返回false if (map2.find(ch) == map2.end() || map2[ch] != count) { return false; } } // 所有字符频次都匹配，返回true return true; } };

为什么要先判断长度？长度不等时，两个字符串的总字符数都不一样，频次统计肯定不可能匹配，提前判断可以避免无效计算。

哈希表的统计逻辑：map1[ch]++：当字符ch第一次出现时，unordered_map会自动创建键值对，默认值为0，执行++后变为1；后续重复出现时，直接对已存在的键值对做自增。 两个哈希表分别统计，完全独立，互不干扰。

对比频次的过程：遍历map1的每个键值对，检查map2中是否存在该键，且值相等。因为两个字符串长度相等，只要map1的所有键都在map2中且频次相等，map2中就不会有多余的键（否则总字符数会不一致），所以不需要再遍历map2。

时间复杂度O（n），空间复杂度O（n）

3. 优化：一个哈希表解法

1） 前置判断：长度校验

如果两个字符串的长度不相等，直接返回 false。
逻辑很简单：字符重排不会改变字符串的长度，长度不同的字符串绝对不可能互为重排。

2） 核心逻辑：字符频次统计

两个字符串互为字符重排的充要条件是：每个字符出现的次数完全相同。
我们可以用一个「计数数组」（本质是哈希表的简化实现）来统计频次：

遍历第一个字符串 s1，统计每个字符出现的次数，存入计数数组。

遍历第二个字符串 s2，每遇到一个字符，就将计数数组中对应的次数减 1。

如果减 1 后次数小于 0，说明 s2 中出现了 s1 没有的字符，或出现次数超过了 s1，直接返回 false。

遍历完成后没有提前返回，说明两个字符串的字符频次完全匹配，返回 true。

class Solution { public: bool CheckPermutation(string s1, string s2) { // 1. 长度不相等，直接返回false if(s1.size() != s2.size()) return false; // 2. 初始化计数数组（对应26个小写字母） int hash[26] = { 0 }; // 3. 统计s1中每个字符的出现次数 for(auto ch : s1) hash[ch - 'a']++; // ch - 'a' 将字符映射到0~25的索引 // 4. 遍历s2，对计数数组做减法校验 for(auto ch : s2) { hash[ch - 'a']--; // 如果出现负数，说明s2有多余的字符，直接返回false if(hash[ch - 'a'] < 0) return false; } // 5. 所有字符频次匹配，返回true return true; } };

4. 关键知识点拆解

1） 为什么用 int hash[26] 而不是 unordered_map？

这是一种数组哈希的优化写法：因为题目默认是小写英文字母，字符范围固定在 'a'~'z'，共 26 个。

用数组计数的优势：

时间效率更高：数组的访问是 O(1)，比 unordered_map 少了哈希计算的开销。

空间更省：固定大小为 26，不需要额外的哈希表结构开销。

逻辑更简单：直接通过 ch - 'a' 就能映射到索引，不需要处理哈希冲突。

2） 为什么 hash[ch - 'a']++ 能统计字符次数？

对于字符 'a'，'a' - 'a' = 0，对应数组索引 0；对于字符 'b'，'b' - 'a' = 1，对应数组索引 1；以此类推，'z' 对应索引 25，刚好覆盖 26 个字母。遍历 s1 时，每遇到一个字符，就给对应索引的计数加 1，最终数组里的值就是每个字符出现的次数。

3） 为什么 hash[ch - 'a'] < 0 就能直接返回 false？

举个例子：s1 = "abc"，s2 = "abb"

遍历 s1 后，hash[0] = 1（a的次数）、hash[1] = 1（b的次数）、hash[2] = 1（c的次数），其余为0。

遍历 s2：第一个 'a'：hash[0]-- → hash[0] = 0，正常。第一个 'b'：hash[1]-- → hash[1] = 0，正常。第二个 'b'：hash[1]-- → hash[1] = -1，此时 hash[1] < 0，说明 s2 中 b 的次数比 s1 多，直接返回 false。

这个提前终止的技巧，能避免遍历完整个字符串，优化了最坏情况下的执行效率。

4） 复杂度分析

时间复杂度：O(N)，其中 N 是字符串的长度，两次遍历字符串的时间都是 O(N)。

空间复杂度：O(1)，计数数组的大小固定为 26，和输入字符串的长度无关，属于常数级空间。

题目3：存在重复元素（LeetCode 217）

1. 题目描述

给你一个整数数组 nums。如果任一值在数组中出现至少两次，返回 true；如果数组中每个元素互不相同，返回 false。

• 示例 1：
输入：nums = [1,2,3,1]
输出：true

• 示例 2：
输入：nums = [1,2,3,4]
输出：false

2. 核心算法思路（哈希集合）

1） 核心逻辑

题目只需要判断是否存在重复元素，不需要统计次数，因此可以用 unordered_set（哈希集合）来实现：

哈希集合的特点：不允许存储重复元素，且插入、查询的时间复杂度都是 O(1) 平均情况。

遍历数组时，边检查边插入：对当前元素 x，检查哈希集合中是否已经存在 x；如果存在，说明出现了重复元素，直接返回 true；如果不存在，将 x 插入哈希集合，继续遍历；遍历结束后都没有返回，说明数组中没有重复元素，返回 false

2） 复杂度分析

时间复杂度：O(N)，其中 N 是数组长度，每个元素只被遍历一次，哈希集合的操作是 O(1) 平均时间。

空间复杂度：O(N)，最坏情况下（数组中没有重复元素），哈希集合需要存储所有 N 个元素。

class Solution { public: bool containsDuplicate(vector<int>& nums) { unordered_set<int> hash; // 哈希集合，存储已遍历过的元素 for(auto x : nums) // 遍历数组中的每个元素 { // 检查当前元素是否已经在集合中 if(hash.count(x)) return true; // 存在重复，直接返回true else hash.insert(x); // 不存在则插入集合 } // 遍历结束仍未发现重复，返回false return false; } };

3. 关键知识点拆解

1） 为什么用 unordered_set 而不是 unordered_map？

unordered_set 是集合，只存储元素本身，不需要额外的键值对结构，空间更省，逻辑也更贴合题目需求。

用 unordered_map 也能实现（比如 map[num]++，如果 count > 1 就返回 true），但会多存一个无用的“次数”值，属于冗余操作。

2） 核心操作解析

hash.count(x)：检查集合中是否存在元素 x，存在返回 1，不存在返回 0，时间复杂度 O(1)。

hash.insert(x)：将元素 x 插入集合，如果集合中已经存在 x，插入操作不会改变集合，但也不会报错，只是返回一个 pair 告知插入是否成功。

边检查边插入的优势：一旦发现重复，立刻终止遍历，不需要遍历完整个数组，优化了最好情况下的执行效率。

题目4：存在重复元素 II （LeetCode 219）

1. 题目描述

给你一个整数数组 nums 和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，满足：

nums[i] == nums[j]，abs(i - j) <= k，如果存在，返回 true；否则，返回 false。

• 示例 1：
输入：nums = [1,2,3,1], k = 3
输出：true
解释：nums[0] 和 nums[3] 都是 1，且 abs(0-3) = 3 <= k

• 示例 2：
输入：nums = [1,0,1,1], k = 1
输出：true
解释：nums[2] 和 nums[3] 都是 1，且 abs(2-3) = 1 <= k

2. 核心算法思路（哈希表+贪心）

1） 核心逻辑

题目需要同时满足两个条件：元素值相同 + 下标差不超过k。
我们用哈希表来解决这个问题：

哈希表的键（key）：存储数组中的元素值 nums[i]

哈希表的值（value）：存储该元素上一次出现的下标 lastIndex

2） 贪心优化（关键！）

遍历数组时，遇到相同元素时，只需要记录它上一次出现的下标，而不需要保存所有历史下标：

如果当前元素 nums[i] 已经在哈希表中：

计算当前下标 i 和上一次出现的下标 hash[nums[i]] 的差 i - hash[nums[i]]

如果差 <= k，直接返回 true

如果差 > k，更新哈希表中该元素的下标为当前 i（因为后续再出现相同元素时，当前下标会比之前的下标更近，更有可能满足条件）

如果当前元素不在哈希表中，直接将 nums[i] 和 i 存入哈希表

3） 遍历结束未返回，说明不存在满足条件的元素，返回 false

class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_map<int, int> hash; // key: 数组元素值, value: 元素上一次出现的下标 for(int i = 0; i < nums.size(); i++) { // 如果当前元素已经存在于哈希表中 if(hash.count(nums[i])) { // 检查下标差是否<=k if(i - hash[nums[i]] <= k) return true; } // 更新当前元素的下标（无论是否存在，都更新为当前下标） hash[nums[i]] = i; } // 遍历结束仍未找到满足条件的元素 return false; } };

3. 关键知识点拆解

1） 为什么只需要记录「上一次出现的下标」？

这是贪心思想的体现：下标是从小到大遍历的，当前下标 i 是最新的，后续再出现相同元素时，与当前下标 i 的差，一定比与之前所有下标的差更小。

举个例子：nums = [1, 2, 1, 1], k=1

i=0：1 不在哈希表，存入 hash[1]=0

i=2：1 存在，差为 2-0=2 > 1，更新 hash[1]=2

i=3：1 存在，差为 3-2=1 <= 1，返回 true

如果不更新下标，i=3 时会和 0 比较，差为 3 > 1，会错误返回 false

2） 复杂度分析

时间复杂度：O(N)，其中 N 是数组长度，每个元素只被遍历一次，哈希表的操作是 O(1) 平均时间

空间复杂度：O(N)，最坏情况下（数组中没有重复元素），哈希表需要存储所有 N 个元素

3） 易错点提醒

不要在差 >k 时不更新下标，否则后续的相同元素会和旧下标比较，导致错误判断

下标差用 i - hash[nums[i]] 即可，因为 i 是递增的，i 永远比 hash[nums[i]] 大，不需要用 abs()

4. 拓展：滑动窗口解法

这道题也可以用滑动窗口结合哈希集合实现，空间复杂度更优：

class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_set<int> window; for (int i = 0; i < nums.size(); ++i) { // 窗口大小超过k，移除窗口最左边的元素 if (i > k) window.erase(nums[i - k - 1]); // 检查当前元素是否在窗口中 if (window.count(nums[i])) return true; window.insert(nums[i]); } return false; } };

时间复杂度：O(N)；空间复杂度：O(k)，哈希集合中最多存储 k+1 个元素

题目5：字母异位词分组（LeetCode 49）

1. 题目描述

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

•示例 1:

输入:strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出:[["bat"],["nat","tan"],["ate","eat","tea"]]

解释：在 strs 中没有字符串可以通过重新排列来形成"bat"。字符串"nat"和"tan"是字母异位词，因为它们可以重新排列以形成彼此。字符串"ate"，"eat"和"tea"是字母异位词，因为它们可以重新排列以形成彼此。

•示例 2:

输入:strs = [""]输出:[[""]]

•示例 3:

输入:strs = ["a"]输出:[["a"]]

•提示：1 <= strs.length <= 104，0 <= strs[i].length <= 100，strs[i]仅包含小写字母

2. 核心算法思路（哈希表 + 排序）

1） 核心逻辑

字母异位词的关键特性：互为字母异位词的两个字符串，排序后的结果一定完全相同。

例如 eat、tea、ate 排序后都是 aet，tan、nat 排序后都是 ant。

我们可以利用这个特性，把排序后的字符串作为哈希表的 key，把原字符串存入对应的 value（字符串数组）中，实现分组。

2） 具体步骤

遍历字符串数组：对每个字符串，生成它的「排序后副本」作为分组键。

存入哈希表：将原字符串存入以「排序后副本」为键的哈希表对应的列表中。

提取结果：遍历哈希表，将所有键对应的列表取出，作为最终结果。

class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { // 哈希表：key为排序后的字符串，value为对应的异位词列表 unordered_map<string, vector<string>> hash; // 1. 遍历所有字符串，按排序后的key分组 for(auto& s : strs) { string tmp = s; // 复制原字符串，避免修改原数据 sort(tmp.begin(), tmp.end());// 对副本进行排序，得到分组key hash[tmp].push_back(s); // 将原字符串存入对应分组 } // 2. 从哈希表中提取所有分组，转为结果格式 vector<vector<string>> ret; for(auto& [key, group] : hash) // C++17结构化绑定，遍历哈希表 { ret.push_back(group); } return ret; } };

3. 关键知识点拆解

1） 为什么用「排序后的字符串」作为哈希表的 key？

这是一种「哈希映射」的技巧，利用排序的结果将所有字母异位词映射到同一个 key 上，实现自动分组。对于任意两个字母异位词，它们排序后的结果必然相同；反之，排序后结果相同的两个字符串，一定是字母异位词（假设字符集相同）。

2） 容器嵌套的理解

这道题的哈希表是 unordered_map<string, vector<string>>，属于容器嵌套：

外层容器：unordered_map，实现 key 到 value 的映射。

内层容器：vector<string>，存储同一组的所有字母异位词。

这种结构的优势是：自动帮我们完成分组，不需要手动维护多个列表。

3） 复杂度分析

时间复杂度：O(N * Klog K)，其中 N 是字符串数组的长度，K 是字符串的平均长度。

每个字符串排序的时间复杂度是 O(K * K)，遍历所有字符串的时间是 O(N)，因此总时间复杂度为 O(N * Klog K)。

空间复杂度：O(N * K)，哈希表需要存储所有字符串的副本，总空间为所有字符串的长度之和。

4. 拓展优化：计数哈希（避免排序）

如果字符串的字符集固定（如仅小写字母），可以用「字符计数」的方式生成 key，避免排序的开销：

class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { // 用字符计数数组作为key（这里用string表示计数，比如"a1b2..."） unordered_map<string, vector<string>> hash; for (auto& s : strs) { int count[26] = {0}; for (char c : s) count[c - 'a']++; // 将计数数组转为字符串作为key string key; for (int i = 0; i < 26; ++i) { key += to_string(count[i]) + "#"; // 用#分隔，避免歧义 } hash[key].push_back(s); } vector<vector<string>> ret; for (auto& p : hash) ret.push_back(p.second); return ret; } };

时间复杂度：O(N * K)，无需排序，仅需两次遍历字符串。

空间复杂度：O(N * K)，和排序法相同。