哈希表核心原理与实战
哈希表是处理数据查找、统计和去重的利器。在 C++ 中,unordered_map 和 unordered_set 提供了平均 O(1) 的访问效率,非常适合应对高频查询场景。
下面我们通过五个经典案例,看看如何灵活运用哈希结构解决实际问题。
两数之和
给定一个整数数组和一个目标值,找出和为目标值的两个数的下标。最直接的想法是暴力枚举,但利用哈希表可以将时间复杂度降为 O(n)。
思路很简单:遍历数组时,计算当前数字需要的补数(target - nums[i]),如果补数已经在哈希表中出现过,说明找到了答案;否则将当前数字及其下标存入表中。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> hash;
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 {-1,-1};
}
};
注意这里先查后存,避免重复使用同一个元素。
字符排列检查
判断两个字符串是否互为字母重排。这本质上是在比较字符频次。
我们可以用一个长度为 26 的数组模拟哈希计数。先统计第一个字符串中每个字符的出现次数,再遍历第二个字符串进行抵消。如果过程中出现负数,或者最终有剩余,说明不匹配。






