核心内容摘要
RexUniNLU镜像免配置实战：docker run一键启动Gradio界面，7大任务交互式调试教程
在 LeetCode 的题目体系中哈希表Hash Table是最常见、最重要的数据结构之一。
它的核心优势是用空间换时间将查找复杂度从 O(n) 降到 O(
。
很多面试高频题都离不开哈希表的思想。
本篇博客将系统
总结三道最经典的哈希表入门题
两数之和Two Sum
字母异位词分组Group Anagrams
最长连续序列Longest Consecutive Sequence并通过这三题掌握哈希表最核心的三种用法✅ 查补数✅ 分组映射✅ 连续序列判断
LeetCode 1两数之和Two Sum
两数之和 - 力扣LeetCode
题目描述给定一个整数数组nums和一个整数目标值target请你找出数组中和为 target 的两个数并返回它们的下标。
示例输入nums [2,7,11,15], target 9 输出[0,1] 解释nums[0] nums[1] 2 7
暴力思路不可取最直观的方法是双重循环for i: for j: if nums[i] nums[j] target时间复杂度O(n²)当 n 达到 10⁵ 时直接超时。
哈希表优化思路核心思想查找补数遍历数组时当前数字为x需要另一个数字need target - x如果之前出现过need说明答案已找到。
因此我们使用哈希表key数字value数字出现的位置
C代码实现class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, int mp; for (int i 0; i nums.size(); i) { int need target - nums[i]; if (mp.count(need)) { return {mp[need], i}; } mp[nums[i]] i; } return {}; } };
复杂度分析操作复杂度遍历数组O(n)哈希查找O(
总复杂度✅ O(n)
LeetCode 49字母异位词分组Group Anagrams
题目描述给定字符串数组strs请你将所有字母异位词分组。
字母异位词字母相同顺序不同示例输入[eat,tea,tan,ate,nat,bat] 输出 [ [eat,tea,ate], [tan,nat], [bat] ]
哈希表的核心分类映射异位词的本质两个字符串是异位词排序后一定完全相同。
例如原字符串排序后eataetteaaetateaet因此可以用key排序后的字符串value所有属于该 key 的字符串集合
解题步骤遍历字符串数组对每个字符串排序得到 key放入哈希表中分类最后输出所有组
C代码实现class Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring, vectorstring mp; for (auto s : strs) { string key s; sort(key.begin(), key.end()); mp[key].push_back(s); } vectorvectorstring result; for (auto p : mp) { result.push_back(p.second); } return result; } };
复杂度分析设n 为字符串数量k 为字符串平均长度排序复杂度O(k log k)总复杂度O(n * k log k)
LeetCode 128最长连续序列Longest Consecutive Sequence
题目描述给定一个未排序整数数组nums找出数字连续的最长序列长度。
要求算法复杂度必须为O(n)示例输入nums [100,4,200,1,3,2] 输出4 解释最长连续序列是 [1,2,3,4]
核心难点排序可以解决sort(nums)但复杂度O(n log n)题目要求必须 O(n)。
哈希集合解法从起点扩展核心思想如果数字x是一个连续序列的起点x - 1 不存在例如序列[1,2,3,4]起点只有 1因为
0 不存在所以用unordered_set存所有数字只从起点开始扩展每个数字最多访问一次
C代码实现class Solution { public: int longestConsecutive(vectorint nums) { unordered_setint st(nums.begin(), nums.end()); int longest 0; for (int x : st) { // 只有当 x 是起点才扩展 if (!st.count(x -
) { int cur x; int len 1; while (st.count(cur
) { cur; len; } longest max(longest, len); } } return longest; } };
复杂度分析操作复杂度建集合O(n)扩展遍历O(n)总复杂度✅ O(n)
三题核心套路
总结题号题目哈希结构核心思想1Two Sumunordered_map查补数49Group Anagramsunordered_mapstring,vector分类映射128Longest Consecutiveunordered_set起点扩展
哈希表题目三大模板模板 1查找补数need target - x; if (mp.count(need)) return ans;模板 2分类映射key transform(x); mp[key].push_back(x);模板 3存在性判断 起点扩展if (!st.count(x-
) { while(st.count(x
) ... }
六、
总结通过这三道经典题你应该掌握哈希表在 LeetCode 中最常见的三种用途✅ 快速查找✅ 分类分组✅ 判断连续关系哈希表题目看似简单但却是面试必考的基础能力。
下一步推荐练习哈希专题如果你想继续刷哈希题可以按顺序练217 存在重复元素242 有效的字母异位词560 和为 K 的子数组347 前 K 个高频元素15 三数之和哈希 双指针