算法入门笔记 哈希表

概念

哈希表是键值对的表。不同于一般的字典，哈希表的值常常是链表。

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 {};
    }
};