【算法】了解哈希表/思想 并用哈希解算法题（C++）

基本了解

哈希表是什么？

一种数据结构，用于存储元素。

有什么用？

用于快速查找元素 与 插入

何时用哈希表？

频率统计、查找（数据和下标）、高效的插入删除等

如何用哈希表

1. 解题时，可以直接使用容器类（unordered_map, unordered_set）
2. 使用数组代替哈希表

解题

1.两数之和

思路

• 题意分析：要求找和为target的两个数，即对于nums[i],只需要找到个值为target-nums[i]的数的下标
• 解法：哈希表
  

代码

vector<int> twoSum(vector<int>& nums, int target) {
    // 哈希
    unordered_map<int, int> hash; // <nums[i], i>
    for(int i = 0; i < nums.size(); ++i)
    {
        int x = target - nums[i];
        if(hash.count(x)) return {hash[x], i}; // 返回下标
        hash[nums[i]] = i;
    }

    return {-1, -1};
}

---

面试题01.02.判定是否互为字符重排

思路

• 题意分析：如果两字符串符合重排，则所有字符一定相同
• 解法：数组代替哈希表
  • 当有类似的比较字符，数组元素，与次数相联系的，都可以尝试使用哈希表
  • 由于题目中字符串只包含小写字母，我们使用大小为26的数组即可
  1. 初始化哈希表所有位为0（哈希表用于记录每个字符的出现次数）
  2. 哈希表首先记录s1字符的出现次数，再将s2中所有字符从hash中减去
  3. 如果hash中存在负数，则证明两字符串所含字符有不同，即不为重排

代码

bool CheckPermutation(string s1, string s2) {
     if(s1.size() != s2.size()) return false; // 字符长度不同，false

     int words[26] = {};
     for(char ch : s1) // 记录s1中字符出现次数
         words[ch - 'a']++;
 
     for(char ch : s2) // 如果有s2中的字符，则哈希--
         words[ch - 'a']--;

     for(int i = 0; i < 26; ++i)
     {
         if(words[i] < 0)    return false; // 如果
     }

     return true;
}

---

217.存在重复元素

思路

• 题意分析：即判断数组是否存在重复元素（这不哈希表？）
• 解法一：排序
  • 直接用sort排序数组后遍历数组比较后一位即可
• 解法二：哈希表
  1. 通过哈希表统计数组中所有元素的出现次数
  2. 遍历哈希表（通过迭代器）找是否有次数 > 1的数

代码

bool containsDuplicate(vector<int>& nums) {
    // 哈希
    unordered_map<int, int> countMap;
    for(int x : nums) // 记录各元素出现次数
        countMap[x]++;

    for(auto it = countMap.begin(); it != countMap.end(); ++it)
    {
        if(it->second > 1) return true;
    }

    return false;
}

---

219.存在重复元素II

思路

• 题意分析：即在数组中找到值相同的两个元素，满足两元素距离 <= k
• 解法：哈希表
  • 解法与两数之和类似
  1. 遍历数组
     • 每次记录当前元素的值，在哈希表中查找是否已有该值
     • 如果存在：判断两个元素的下标是否<=k
     • 如果不存在，将当前元素加入到哈希表中
  2. 数组遍历结束，找不到满足条件的，返回false

代码

bool containsNearbyDuplicate(vector<int>& nums, int k) {
    unordered_map<int, int> countMap;

    // 遍历数组，如果该数出现在哈希表，则代表重复：判断下标是否满足条件
    // 未出现在哈希表，则加入哈希表
    for(int i = 0; i < nums.size(); ++i)
    {
        int x = nums[i];
        if(countMap.count(x) && i - countMap[x] <= k)   
            return true;
        countMap[x] = i; 
    }
    return false;
}

---

49.字母异位词分组

思路

• 题意分析：字母异位词即满足字符重拍的两字符串，将给定的字符串数组按照字母异位词分组
• 解法：哈希表（存储分类后的结果vector<string>）
  1. 将字母异位词存入哈希表
     • 遍历strs，提取每个字符串并排序，将排序后的结果加入到哈希表中
     • 遍历执行完毕，此时所有的字母异位词都在哈希表中分了类
  2. 提取哈希表中的字符串到结果数组
     • 直接利用auto [x, y] 提取出hash中的y
     • 即所有字母异位词的分组（vector<string>）

代码

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> hash;
    
    // 将字母异位词分类放入哈希表
    for(string s : strs)
    {  
        string tmp = s;
        sort(tmp.begin(), tmp.end());
        hash[tmp].push_back(s);
    }

    vector<vector<string>> ret;
    // 提取字符串到数组
    for(auto& [x, y] : hash) // [x, y]，指代哈希表的两个类型
    {
        ret.push_back(y);
    }
    return ret;
}