【LeetCode】哈希表精选5题

目录

1. 两数之和（简单）

2. 验证外星语词典（简单）

3. 存在重复元素（简单）

4. 存在重复元素 II（简单）

5. 字母异位词分组（中等）

1. 两数之和（简单）

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

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        unordered_map<int, int> hash; // key——nums[i] value——i
        for (int i = 0; i < n; i++)
        {
            int x = target - nums[i];
            if (hash.count(x))
                return { hash[x],i };
            hash[nums[i]] = i;
        }
        return { -1,-1 };
    }
};

2. 验证外星语词典（简单）???????

用数组模拟哈希表，hash[0]表示字母'a'在字母表中的顺序，hash[1]表示字母'b'在字母表中的顺序……

为了判断两个单词是否是按照字母表的顺序排序的，可以扫描两个单词中的字母找出第一个不相同的字母。哪个单词的第一个不相同的字母在字母表中的位置靠前，排序的时候它就排在前面。如果没有找到不相同的字母，那么短的单词在排序的时候应该排在前面。

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        // 初始化哈希表
        for (int i = 0; i < order.size(); i++)
        {
            hash[order[i] - 'a'] = i;
        }
        // 判断相邻的两个单词是否按照字母表的顺序排序
        for (int i = 0; i < words.size() - 1; i++)
        {
            if (!isSorted(words[i], words[i + 1]))
                return false;
        }
        return true;
    }

private:
    bool isSorted(string& word1, string& word2)
    {
        int i = 0;
        while (i < word1.size() && i < word2.size())
        {
            char ch1 = word1[i];
            char ch2 = word2[i];
            if (ch1 == ch2)
            {
                i++;
            }
            else
            {
                if (hash[ch1 - 'a'] < hash[ch2 - 'a'])
                    return true;
                if (hash[ch1 - 'a'] > hash[ch2 - 'a'])
                    return false;
            }
        }
        return i == word1.size();
    }

    int hash[26]; // 记录字母在字母表中的顺序
};

3. 存在重复元素（简单）

出现至少两次就是数组中存在着重复的元素，因此我们可以无需统计元素出现的数目。仅需在遍历数组的过程中，检查当前元素是否在之前已经出现过即可。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> hash;
        for (auto& e : nums)
        {
            if (hash.count(e))
                return true;
            else
            {
                hash.insert(e);
            }
        }
        return false;
    }
};

4. 存在重复元素 II（简单）

创建一个哈希表，对于每一个nums[i]，我们首先查询哈希表中是否存在nums[i]，并且i - hash[nums[i]] <= k，然后将nums[i]插入到哈希表中，即可保证不会让nums[i]和自己匹配。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> hash; // key——nums[i] value——i
        for (int i = 0; i < n; i++)
        {
            int x = nums[i];
            if (hash.count(x) && i - hash[x] <= k)
                return true;
            hash[x] = i;
        }
        return false;
    }
};

5. 字母异位词分组（中等）

把一组字母异位词映射到同一个单词，由于互为字母异位词的单词的字母出现的次数分别相同，因此如果把单词中的字母排序就会得到相同的字符串。

创建一个哈希表，key为把单词字母排序得到的字符串，value为一组字母异位词。

例如，eat tea ate -> aet，创建哈希表，key——"aet"，value——{ "eat","tea","ate" }。

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