LeetCode 热题 100 | 哈希

这篇具有很好参考价值的文章主要介绍了LeetCode 热题 100 | 哈希。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1 基础知识

1.1 定义哈希表

1.2 遍历哈希表

1.3 查找某一个键

1.4 插入键值对

1.5 获取键值对的值

1.6 搜索功能

2 三道题

2.1 1. 两数之和

2.2 49. 字母异位词分组

2.3 128. 最长连续序列

菜鸟做题第一周，语言是 C++

1 基础知识

1.1 定义哈希表

unordered_map<string, vector<string>> hashtable;

unordered_map 用于定义哈希表
第一个参数为 key 的数据类型，这里是 string 类型
第二个参数为 value 的数据类型，这里是 vector<string> 类型

1.2 遍历哈希表

for (auto str:hashtable) {
    // code
}

这种遍历方法对其他容器也适用
冒号后写遍历的对象，这里是 hashtable
冒号前写被遍历到的元素，这里取名为 str

1.3 查找某一个键

auto it = hashtable.find(target);
if (it != hashtable.end()) {
    // code
}

find() 的参数是想要查找的 key
it 是本次查找的结果
若没有找到，则 it 等于 hashtable.end()
hashtable.end() 是哈希表最后一个元素的后一位

1.4 插入键值对

// 方法一
hashtable[key] = value;
// 方法二
hashtable[key].push_back(value);

目前看到过上述两种方法
key 处填写键，value 处填写值

这是看人下碟，暂时还不太懂

1.5 获取键值对的值

// 方法一
str->second
// 方法二
str.second

同样看到过两种方法
str 是哈希表中的某一键值对
second 代表想要获取的是 value

1.6 搜索功能

作用：搜索某个键是否存在于哈希表内。

hashtable.count(key)

count 的作用是搜索而不是计数
key 代表想要搜索的键
若存在该键，则返回值为 1

2 三道题

2.1 1. 两数之和

解题思路：

遍历数字集合 nums
查询是否有和为 target 的另一个数字

思路说明图：

这里假设 target=9
将暂时没找到伴儿的数字放入哈希表中

LeetCode 热题 100 | 哈希,力扣,哈希算法,leetcode,算法

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

可能出现的问题：

LeetCode 热题 100 | 哈希,力扣,哈希算法,leetcode,算法

虽然题设表明一定能找到一对和为 target 的数字，但力扣比较严谨，它要求 if 判断结构中的 else 情况也要进行返回（虽然用不到）。

2.2 49. 字母异位词分组

解题思路：

遍历 strs 中的每一个字符串
使用 sort 函数对这些字符串进行重新排序
排序前的字符串作为 key，排序后的字符串作为 value，插入到哈希表中
哈希表中每个键值对的 value 的集合即为最终的结果

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> result;
        unordered_map<string, vector<string>> hashtable;
        for (auto str:strs) {
            auto temp = str;
            sort(temp.begin(), temp.end());
            hashtable[temp].push_back(str);
        }
        for (auto str:hashtable) {
            result.push_back(str.second);
        }
        return result;
    }
};

这个涉及到哈希表的原理，即 key 相同时，如何存储不同的 value，暂时还没看

2.3 128. 最长连续序列

解题思路：

遍历 nums 寻找可能成为序列头的数字（不能存在 num - 1）
若找到可能成为序列头的数字，则顺着它找序列并计数（哈希表找 num + 1）
每计数完一条序列的长度都要和之前序列的长度进行比较（cucount 和 count）
返回最长的长度（count）

思路说明图：

LeetCode 热题 100 | 哈希,力扣,哈希算法,leetcode,算法

思考过程：

一开始想的是找序列中最小的那个数字（我理所应当地认为它就是序列头），然后以它为开头去找序列并计数，但 nums 中可能存在不止一条连续序列，因此我们需要考虑所有可能的序列头。

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

        int count = 1;
        unordered_map<int, int> hashmap;
        for (int i = 0; i < nums.size(); ++i) {
            hashmap[nums[i]] = i;
        }
        for (auto num:nums) {
            auto it = hashmap.find(num - 1);
            if (it == hashmap.end()) {
                int cucount = 1;
                it = hashmap.find(num + cucount);
                while (it != hashmap.end()) {
                    ++cucount;
                    it = hashmap.find(num + cucount);
                }
                count = max(count, cucount);
            }
        }
        return count;
    }
};