概念
哈希表是键值对的表。不同于一般的字典,哈希表的值常常是链表。
key value
0 []
1 [1->2->3->4]
2 [2->3->4]
3 []
计算 key 的方法有很多。例如取余数。
使用
在 C++ 中,哈希表对应的是 std 的 unordered_map
, hash_map
。
hash_map<int, string> map; //初始化哈希表
map[123]="my string"; // 插入数据
map.find(666); // 查找数据,找不到返回 map.end()
应用
举个 leetcode 的例子:
两数之和
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
不使用哈希表的解法如下:
class Solution
{
public:
vector<int> twoSum(vector<int> &nums, int target)
{
int count = nums.size();
for (int i = 0, j = 1; i < count; ++i && ++j)
{
while (j != count && nums[i] + nums[j] != target)
{
j++;
}
if (j == count)
{
j = i + 1;
continue;
}
return {i, j};
}
return {};
}
};
使用哈希表的思路如下:
用一个循环进行遍历,
把所有遍历过的数字都作为 key 放入哈希表。他们的下标作为 value 放入哈希表。
当找到时,设找到的数字时 k,此时的下标为 arr[i]
,则有 arr[i] + k = target
成立。
所以我们只需要每次遍历都判断 k = target - arr[i]
是否存在。存在的话就返回 k 的下标和 i 即可。
代码如下:
class Solution
{
public:
vector<int> twoSum(vector<int> &nums, int target)
{
int size = nums.size();
unordered_map<int, int> map;
map[nums[0]] = 0;
for (int i = 1; i < size; i++)
{
if(map.find(target - nums[i])!=map.end()){
return{map[target - nums[i]], i};
}
map[nums[i]] = i;
}
return {};
}
};