LeetCode Hot 100 的哈希表题目实战整理

2. 字母异位词分组

这题的关键在于：字母异位词的字母组成一样，只是顺序不同。最稳的做法是先把每个字符串排序，排序后的结果作为键，原字符串作为值放进哈希表里。最后把哈希表里的值取出来，就是分组结果。

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

这里用的是 string，不是 int。哈希表的结构很清楚："aet" -> ["eat", "tea", "ate"]，所以类型就是 unordered_map<string, vector<string>>。

operator[] 的好处是，如果键不存在，它会自动创建一个默认值。这个题里配合 push_back 用起来很顺手。

emplace_back 和 push_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. 最长连续序列

这题的思路很固定：先把所有数字丢进哈希集合去重，然后只从'起点'开始往后数。所谓起点，就是 n - 1 不存在的那个数。不是起点的数字没必要再数一遍，不然会把复杂度拖上去。

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

longestLength 的更新要放在起点判断里面，不然就会多算很多重复链条。

如果数组里有重复元素，直接遍历 set 也行；原理一样，只是少一些重复判断。下面这个版本更干净一点：

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

这三题放在一起看，其实就是同一类思路：用哈希结构把'查找'这件事压到很低的成本，再根据题目要求决定存什么。两数之和存值和下标，异位词分组存排序后的字符串，最长连续序列存集合。题不一样，套路倒是很统一。