力扣hot100哈希表专题解析（C++）

最近在备战蓝桥杯，刷力扣的 Hot 100 题目，想和大家分享几道关于哈希表的经典题目。这几道题覆盖了哈希表的几个核心应用场景，解题过程中也让我对哈希表有了更深的理解。下面我将分享每道题的解题心路历程和代码实现。如果对其中的一些基本用法有疑问的朋友也可以参考我之前写的一个简单用法总结备战蓝桥杯-哈希。

一、两数之和：从暴力枚举到哈希优化

（只有一个有效答案）

这道题的要求很明确：在一个整数数组中找到两个数，使它们的和等于给定的目标值，并返回这两个数的下标。

我的第一反应是暴力枚举，用两层循环遍历所有可能的组合。但这样的时间复杂度是 O(n²)，我们需要更高效的方法。

解题的关键在于：当我们遍历数组时，对于当前的数字 nums[i]，我们其实想知道的是 target – nums[i] 这个值是否在数组中出现过，以及它的位置在哪里。如果能快速查询到这个信息，问题就简单了。

这时哈希表就派上用场了。我可以用一个哈希表来记录每个数字和它对应的下标。在遍历过程中，对于每个数字，先检查 target – nums[i] 是否已经在哈希表中，如果在，直接返回结果；如果不在，就把当前数字和下标存入哈希表，继续遍历。

这样只需要遍历一次数组，时间复杂度降到了 O(n)。需要注意的一点是，题目要求不能使用相同的元素两次，但由于我们是边查边存，且先查询后存储，所以不会出现使用同一个元素两次的情况。

cpp

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashMap;
for(int i = 0; i < nums.size(); i++) {
int complement = target – nums[i];
if(hashMap.find(complement) != hashMap.end()) {
return {i, hashMap[complement]};
}
hashMap[nums[i]] = i;
}
return {};
}
};

二、字母异位词分组：设计哈希表的键

（只有小写字母）

这道题要把字母异位词（由相同字母重排形成的词）分到同一组。初看题目，可能会觉得需要逐个比较字符串是否互为字母异位词，但那样效率太低。

关键在于找到一个方法，能让所有字母异位词具有相同的“特征”，然后以这个特征作为哈希表的键。最直接的想法是把每个字符串排序，因为排序后的字母异位词会变成相同的字符串。

比如，"eat"、"tea"、"ate" 排序后都变成 "aet"。这样我就可以用排序后的字符串作为键，把原始字符串作为值存入哈希表。遍历完所有字符串后，哈希表中每个键对应的值列表就是一组字母异位词。

这种方法的巧妙之处在于，它把比较字母异位词的复杂度降低了。

cpp

class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> hashMap;

for(string &str : strs) {
string key = str;
sort(key.begin(), key.end());
hashMap[key].push_back(str);
}

vector<vector<string>> result;
for(auto &pair : hashMap) {
result.push_back(pair.second);
}

return result;
}
};

三、最长连续序列：哈希集合的妙用

这道题要求找出数字连续的最长序列长度，并且要求 O(n) 时间复杂度。最直接的想法是先排序，然后遍历统计连续序列的长度，但是不能sort排序或者set自动排序（排序是 O(n log n)），需要利用哈希集合（unordered_set）来实现。

哈希集合提供了 O(1) 的查找能力。我可以先把所有数字存入集合去重。然后遍历集合中的每个数字，但我只关心那些可能是序列起点的数字——即它的前一个数字不在集合中。

对于每个可能的起点，我向后连续查找，直到找不到下一个数字为止，这样就得到了以这个数字为起点的连续序列长度。在遍历过程中记录最大长度即可。

这种方法之所以是 O(n)，是因为每个数字最多被访问两次：一次是作为序列起点被检查，一次是作为序列中间元素被跳过（因为如果它前一个数字存在，它就不会作为起点被处理）。

cpp

class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.empty()) return 0;

unordered_set<int> numSet(nums.begin(), nums.end());
int longest = 1;

for(int num : numSet) {
// 只从可能的序列起点开始
if(!numSet.count(num – 1)) {
int currNum = num;
int currLong = 1;

// 向后延伸序列
while(numSet.count(currNum + 1)) {
currNum++;
currLong++;
}

longest = max(longest, currLong);
}
}

return longest;
}
};

四、解题心得与注意事项

通过这三道题，我对哈希表的理解更加深入了。哈希表的核心价值在于提供 O(1) 的查找能力，这在优化算法时非常关键。

几点提醒：

哈希表确实是算法竞赛中的利器。它能把很多看似复杂的问题简化，把 O(n²) 的暴力解法优化到 O(n)。但也要注意哈希表的空间开销，以及在处理自定义类型时需要提供哈希函数等问题。

这三道题从不同角度展示了哈希表的应用，既有直接的查找优化，也有巧妙的键设计，还有结合集合特性的高效算法。掌握这些模式后，遇到类似问题就能快速想到合适的解法了。