LeetCode Hot 100 哈希表经典题目解析

1. 两数之和

思路与解法

当遍历到某一元素时，比如 3，当要求两数之和为 9 时，需要看 6 在之前有没有出现过，也就是某元素是否出现在这个集合中，那么我们就应该想到使用哈希法了。

因为本题我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key、value 结构来存放，key 来存元素，value 来存下标，那么使用 map 正合适。

这道题目中并不需要 key 有序，选择 std::unordered_map 效率更高！

Map 的目的：

是用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（即相加等于 target）。

Map 中 key 和 value 分别表示什么：

在 map 里：

• key：键，用来查找，本题为元素的值
• value：值，表示这个键对应的数据，本题为元素对应的索引

这道题我们需要给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。

那么判断元素是否出现，这个元素的值就作为 key，因为 map 的作用是最快地查找 key 是否在 map 中出现过。所以数组中的元素作为 key，有 key 对应的就是 value，value 用来存下标。所以 map 中的存储结构为 {key: 数据元素，value: 数组元素对应的下标}。

在遍历数组的时候，只需要向 map 去查询是否有和目前遍历元素匹配的数值，如果有，就找到了匹配对，如果没有，就把目前遍历的元素放进 map 中，因为 map 存放的就是我们访问过的元素。

整体思路：定义 unordered_map——寻找，找到返回，未找到就添加——最终没有匹配的返回空！

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

【注】

1. map.find(…)：unordered_map 的成员函数，用于查找指定的键。参数是要查找的键（key），返回一个迭代器（pair<const Key, Value> 类型）。
2. unordered_map 是一个键值对（key-value pair）容器，它存储的元素实际上是 pair<const Key, Value> 类型的对象。用 map.insert({nums[i], i}) 更简洁！！
3. 如果代码开头有 using namespace std，则不需要加 std::，leetcode 平台模板通常包含 using namespace std。
4. 为何 return {iter->second, i}？因为要求返回的是满足条件的两个元素的数组下标，即 value。iter->first 访问的是 pair<const Key, Value> 中的 Key 部分，存放数组中的元素值；iter->second 访问的是 pair<const Key, Value> 中的 Value 部分，存放索引。

map.insert({nums[i], i}); 添加时是将当前元素的键值加入！！

完整代码示例

#include<bits/stdc++.h>
using namespace std;

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

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    Solution solution;
    vector<int> result = solution.twoSum(nums, target);
    cout << result[0] << " " << result[1] << endl;
    return 0;
}

2. 字母异位词分组

思路及解法

字母异位词的特点是，它们的字母组成相同，只是排列顺序不同。 因此，可以通过对每个字符串进行排序（按从小到大的顺序排列），将排序后的字符串作为键，将原始字符串作为值存入哈希表中。最后，将哈希表中的值提取出来，即为分组后的结果。

核心代码：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;
        for (string& str : strs) {
            string key = str; // 复制一个 key 出来再排序，避免影响原字符串
            sort(key.begin(), key.end());
            map[key].push_back(str);
        }
        vector<vector<string>> result;
        for (auto it = map.begin(); it != map.end(); it++) {
            result.push_back(it->second); // 将哈希 map 的值输出即为结果
        }
        return result;
    }
};

思路：定义哈希 map——取输入的每个字符串，复制后排序作为键，原字符串作为值存入哈希 map——从哈希 map 中取值即为结果

【注】

1. 这里都是 string。别写成 int 了！！ 哈希 map 例子：mp["aet"] = ["eat", "tea", "ate"] 键 aet（string 类型）对应的值为 "eat", "tea", "ate"（vector<string> 类型） 因此 map 为 <string, vector<string>> 类型
2. operator[] 会自动创建默认值
3. emplace_back 是 C++ 容器里的一个尾部插入函数，是把构造对象需要的参数直接传进去，让容器在尾部原地构造。 和 push_back 的区别：push_back 是把一个已经存在的对象塞进去。 什么情况下 emplace_back 更有优势？当元素类型比较复杂时，更明显。

完整代码示例

#include<bits/stdc++.h>
using namespace std;

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

int main() {
    int n;
    cin >> n;
    vector<string> str(n);
    for (int i = 0; i < n; i++) {
        cin >> str[i];
    }
    Solution solution;
    vector<vector<string>> result = solution.groupAnagrams(str);
    for (auto i : result) {
        for (auto j : i) {
            cout << j << " ";
        }
        cout << endl;
    }
    return 0;
}

3. 最长连续序列

思路与解法

核心思想就两步：

1. 先把所有数字放进哈希集合 unordered_set（会自动去重）
2. 判断哈希集合中 num - 1 是否存在，不存在说明 num 是一个起点（一定要从起点开始！！），然后不断查 num + 1、num + 2、num + 3 是否存在，统计这一段连续长度

核心代码：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;
        unordered_set<int> set(nums.begin(), nums.end());
        int longestLength = 0;
        for (int n : nums) {
            if (set.find(n - 1) == set.end()) {
                int currentNum = n;
                int currentLength = 1;
                while (set.find(currentNum + 1) != set.end()) {
                    currentNum++;
                    currentLength++;
                }
                longestLength = longestLength < currentLength ? currentLength : longestLength;
            }
        }
        return longestLength;
    }
};

【注】

1. longestLength = longestLength < currentLength ? currentLength : longestLength; 要写在 if(set.find(n-1)==set.end()){} 循环里

完整代码示例

#include<iostream>
#include<unordered_set>
#include<vector>
using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;
        unordered_set<int> set(nums.begin(), nums.end());
        int longestLength = 0;
        for (int n : set) {
            if (set.find(n - 1) == set.end()) {
                int currentNum = n;
                int currentLength = 1;
                while (set.find(currentNum + 1) != set.end()) {
                    currentNum++;
                    currentLength++;
                }
                longestLength = longestLength < currentLength ? currentLength : longestLength;
            }
        }
        return longestLength;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> res(n);
    for (int i = 0; i < n; i++) {
        cin >> res[i];
    }
    Solution solution;
    cout << solution.longestConsecutive(res) << endl;
    return 0;
}

【注】

1. for(int n : set){ 注意是从 set 中取！！！