【基础算法】哈希表

系列综述：
💞目的：本系列是个人整理为了秋招算法的，整理期间苛求每个知识点，平衡理解简易度与深入程度。
🥰来源：材料主要源于代码随想录进行的，每个算法代码参考leetcode高赞回答和其他平台热门博客，其中也可能含有一些的个人思考。
🤭结语：如果有帮到你的地方，就点个赞和关注一下呗，谢谢🎈🎄🌷！！！
🌈【C++】秋招&实习面经汇总篇

😊点此到文末惊喜↩︎

哈希表理论基础

基础知识

1. 哈希表基本原理

基本用法

1. unordered_set的条件遍历

   unordered_set<int> set;     
   if (set.find(val) != set.end()){
   	// 找到val
       doing();
   }else{
   	// 没找到，插入或者做其他
       set.insert(val);
   }
   

2. 将含重复元素的容器转化为unordered_map

   vector<int> vec = {1,1,3,4,5,5,5};
   unordered_map<int, int> umap; 
   for(const auto &i : vec){
   	umap[i]++;// 有键值i则将其值+1，没有则插入
   }
   

3. unordered_map中对于值的访问和更改

   unordered_map<char, int> umap;
   unordered_map<char, int>::iterator itr;
   for(const auto &c : str){
       itr = umap.find(c);
       if(itr != umap.end())
           doing(itr->second);
          
   }
   

相关算法题目

有效的字母异位词

1. 242. 有效的字母异位词
   

   bool isAnagram(string s, string t) {
       if(s.length() != t.length())
           return false;
       // 建立s字符串的无序哈希表
       unordered_map<char, int> setS;
       for(const auto &c : s){
           setS[c]++;
       }
       // 查询t中数据元素再s中的情况
       unordered_map<char, int>::iterator itr;
       for(const auto &ref: t) {
           // 找到执行值的减减
           itr = setS.find(ref);
           if(itr != setS.end()) {
               itr->second--;
               if(itr->second < 0)
                   return false;
           }else
               return false;
       }
       return true;
   }
   

两个数组的交集

1. leetcode题目：349. 两个数组的交集
   

   vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
       unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
       unordered_set<int> nums_set(nums1.begin(), nums1.end());
       for (int num : nums2) {
           // 发现nums2的元素 在nums_set里又出现过
           if (nums_set.find(num) != nums_set.end()) {
               result_set.insert(num);
           }
       }
       return vector<int>(result_set.begin(), result_set.end());
   }
   // 数组方式实现
   vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
       unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
       int hash[1005] = {0}; // 默认数值为0
       for (int num : nums1) { // nums1中出现的字母在hash数组中做记录
           hash[num] = 1;
       }
       for (int num : nums2) { // nums2中出现话，result记录
           if (hash[num] == 1) {
               result_set.insert(num);
           }
       }
       return vector<int>(result_set.begin(), result_set.end());
   }
   

快乐数

1. 快慢指针

   • 判断循环可以使用，快指针两倍于慢指针速度

2. leetcode题目：27. 移除元素
   

   int bitSquareSum(int n) {
       int sum = 0;
       while(n > 0)
       {
           int bit = n % 10;
           sum += bit * bit;
           n = n / 10;
       }
       return sum;
   }
   // 快慢指针法
   bool isHappy(int n) {
       int slow = n, fast = n;
       do{
           slow = bitSquareSum(slow);
           fast = bitSquareSum(fast);
           fast = bitSquareSum(fast);
       }while(slow != fast);
       
       return slow == 1;
   }
   // 哈希法
   bool isHappy(int n) {
       unordered_set<int> set;
       while(1) {
           int sum = getSum(n);
           if (sum == 1) {
               return true;
           }
           // 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
           if (set.find(sum) != set.end()) {
               return false;
           } else {
               set.insert(sum);
           }
           n = sum;
       }
   }
   

两数之和

1. leetcode题目：1. 两数之和
   

   vector<int> twoSum(vector<int>& nums, int target) {
       std::unordered_map <int,int> map;
       for(int i = 0; i < nums.size(); i++) {
           // 遍历当前元素，并在map中寻找是否有匹配的key
           auto iter = map.find(target - nums[i]); 
           if(iter != map.end()) {
               return {iter->second, i};// 返回含两个int类型元素的vector
           }
           // 如果没找到匹配对，就把访问过的元素和下标加入到map中
           map.insert(pair<int, int>(nums[i], i)); // 构造map数据项
       }
       return {};
   }
   

四数相加II

1. leetcode题目：四数相加
   

   int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
       unordered_map<int, int> umap; //key:a+b的数值，value:a+b数值出现的次数
       // 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
       for (int a : A) {
           for (int b : B) {
               umap[a + b]++;
           }
       }
       int count = 0; // 统计a+b+c+d = 0 出现的次数
       // 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话
       // 就把map中key对应的value也就是出现次数统计出来。
       for (int c : C) {
           for (int d : D) {
               if (umap.find(0 - (c + d)) != umap.end()) {
                   count += umap[0 - (c + d)];
               }
           }
       }
       return count;
   }
   

🚩点此跳转到首行↩︎

参考博客

1. leetcode二分查找
2. 代码随想录
3. 二分查找算法详解
4. 待定引用
5. 待定引用
6. 待定引用
7. 待定引用
8. 待定引用