LeetCode 热题 100-哈希表

两数之和

哈希表

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。

创建一个哈希表，对于每一个 x，首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 定义哈希表
        unordered_map<int, int> hash;
        for(int i = 0; i < nums.size(); i++){
            if(hash.find(target - nums[i]) != hash.end()){
                return {i, hash[target - nums[i]]};
            }
            hash[nums[i]] = i;
        }
        return {};
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

字母异位词分组

排序

把每个单词进行排序，异位词排序后的结果是一样的。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;
        for(string& s : strs){
            string sortedS = s;
            sort(sortedS.begin(), sortedS.end());
            hash[sortedS].push_back(s);
        }

        // 返回结果
        vector<vector<string>> ans;
        for(auto &[_, value] : hash){
            ans.push_back(value);
        }

        return ans;
    }
};

• 时间复杂度：O(nklogk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。
• 空间复杂度：O(nk)

计数

对于每个字符串，首先使用哈希表统计每个字母出现的频率，然后将频率表转换为字符串作为键。这样处理完之后就得到与上一种方法类似的哈希表。最后将哈希表中的结果移到结果数组中。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;

        for(const string& s : strs){
            // 统计字符数
            vector<int> cnt(26);
            for(char ch : s){
                cnt[ch - 'a']++;
            }
            // 将频率转换成字符串
            string freq;
            for(int i = 0; i < 26; i++){
                freq += '#' + to_string(cnt[i]);
            }
            hash[freq].push_back(s);
        }
        // 返回结果
        vector<vector<string>> ans;
        for(auto& [_, value] : hash){
            ans.push_back(value);
        }
        return ans;
    }
};

• 时间复杂度：O(nk)
• 空间复杂度：O(nk)

最长连续序列

哈希表

1. 先将数组存储到集合中进行去重，用变量curLen和ans记录当前序列和最长序列的长度。
2. 遍历集合，判断当前元素num的num-1是否在集合中，如果不在集合中，说明num是序列的起始，如果在集合中，直接跳过。
3. 对于起始元素num，判断num+1,num+2,…是否在集合中，并更新序列长度，最后更新ans。
4. 返回ans。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int ans = 0;
        // 用集合进行去重
        unordered_set<int> set;
        for(const int& num : nums){
            set.insert(num);
        }
        // 遍历集合
        for(const int& num : set){
            // 确定序列起始
            if(!set.count(num - 1)){
                int curLen = 1, curNum = num;
                while(set.count(curNum + 1)){
                    curNum++;
                    curLen++;
                }
                // 更新最大长度
                ans = max(ans, curLen);
            }
        }
        return ans;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

并查集

在刷剑指offer时还用过并查集的方法，这里仅复习一遍思路，因为其实现起来要比上面的方法复杂一些。简单理解，每个序列的起始相当于并查集的父亲。具体见这里。