• 哈希表-算法总结

    目录

    哈希表理论基础

    有效的字母异位词

    两个数组的交集

    快乐数

     两数之和

    四数相加Ⅱ

    三数之和

    四数之和

    哈希表理论基础

    在做哈希表类型题目时，有三种数据结构：数组，set，map。

    数组：用于数值小，范围小的情况，比如26个字母次数

    set：用于数值较大

    map：用于value映射为字符串时。比如班级同学名字

    关于更多理论知识可以参考下面链接：代码随想录 (programmercarl.com)https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E5%93%88%E5%B8%8C%E8%A1%A8


    代码随想录 (programmercarl.com)https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E6%80%BB%E7%BB%93.html

    有效的字母异位词

    该类题目就是统计两个字符串的字母次数，由于26个字母数量较少，我们采用数组形式。

    定义一个26大小的数组，且初始化为0

    1.  vector<int> vec(26, 0);
    2.  int record[26] = {0};

    遍历第一个字符串，把字符串字母数量统计，再遍历第二个字符串，减去该字符串中的字母，再遍历数组，判断元素是否为0，因此整个代码如下：

    1. class Solution {
    2. public:
    3.     bool isAnagram(string s, string t) {
    4.        vector<int> vec(26, 0);
    5.        for(int i = 0; i < s.size(); i++){
    6.            vec[s[i] - 'a']++;
    7.        }
    8.        for(int i = 0; i < t.size(); i++){
    9.            vec[t[i] - 'a']--;
    10.        }
    11.        for(int i = 0; i < 26; i++){
    12.            if(vec[i] != 0){
    13.                return false;
    14.            }
    15.        }
    16.        return true;
    17.  
    18.     }
    19. };

    map版本

    1. class Solution {
    2. public:
    3.     bool isAnagram(string s, string t) {
    4.       unordered_map<char,int>map;
    5.       for(auto &ch : s){
    6.           map[ch]++;
    7.       }
    8.       for(auto &ch : t){
    9.           map[ch]--;
    10.       }
    11.       for(auto num : map){
    12.           if(num.second != 0){
    13.               return false;
    14.           }
    15.       }
    16.       return true;
    17.     }
    18. };

    相关题目：

    242. 有效的字母异位词 - 力扣（LeetCode）https://leetcode.cn/problems/valid-anagram/383. 赎金信 - 力扣（LeetCode）https://leetcode.cn/problems/ransom-note/

    两个数组的交集

    针对字符串中重复出现的数字，如果数字大小有规定则可以数组，否则set或者map

    数组方法：

    1. class Solution {
    2. public:
    3.     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    4.         vector<int>ans(1005,0);
    5.         unordered_set<int>un_set;
    6.         for(auto num : nums1){
    7.             ans[num] = 1;
    8.         }
    9.         for(auto num : nums2){
    10.             if(ans[num] == 1){
    11.                 un_set.insert(num);
    12.             }
    13.         }
    14.         return vector<int>(un_set.begin(),un_set.end());
    15.     }
    16. };

    set方法：

    1. class Solution {
    2. public:
    3.     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    4.         unordered_set<int> ans;
    5.         unordered_set<int> nums_set(nums1.begin(),nums1.end());//插入nums1到nums_set中
    6.         //此时nums1中没有重复的元素，遍历nums2，看nums1中有没有
    7.         for(auto num : nums2){
    8.             if(nums_set.find(num) != nums_set.end()){
    9.                 ans.insert(num);
    10.             }
    11.         }
    12.         return vector<int>(ans.begin(),ans.end());
    13.     }
    14. };

    map方法：

    1. class Solution {
    2. public:
    3.     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    4.         std::unordered_map<int, int> map;
    5.         vector<int> ans;
    6.         for (int i = 0; i < nums1.size(); i++) {
    7.             map[nums1[i]] = 1;
    8.         }
    9.  
    10.         for (int i = 0; i < nums2.size(); i++) {
    11.             if (map[nums2[i]] == 1) {
    12.                 map[nums2[i]] = 0;
    13.                 ans.push_back(nums2[i]);
    14.             }
    15.         }
    16.         return ans;
    17.     }
    18. };

    相关题目：

    349. 两个数组的交集 - 力扣（LeetCode）https://leetcode.cn/problems/intersection-of-two-arrays/

    快乐数

    本题主要包括两个方面：求得每次的和，以及判断和是否重复。

    定义一个求和函数，求得该数的平方和

    1.     int getSum(int n){
    2.         int sum = 0;
    3.         while(n){
    4.             sum += (n % 10) * (n % 10);
    5.             n /= 10;
    6.         }
    7.         return sum;
    8.     }

    对每次的结果进行为1判断，以及是否重复判断。

    1. class Solution {
    2. public:
    3.     int getSum(int n){
    4.         int sum = 0;
    5.         while(n){
    6.             sum += (n % 10) * (n % 10);
    7.             n /= 10;
    8.         }
    9.         return sum;
    10.     }
    11.     bool isHappy(int n) {
    12.         unordered_set<int>un_set;
    13.         while(1){
    14.             int sum = getSum(n);
    15.             if( sum == 1){
    16.                 return true;
    17.             }
    18.             if(un_set.find(sum) != un_set.end()){
    19.                 //出现了这个数
    20.                 return false;
    21.             }else{
    22.                 un_set.insert(sum);
    23.             }
    24.             n = sum;
    25.         }
    26.     }
    27. };

    相关题目：
    202. 快乐数 - 力扣（LeetCode）https://leetcode.cn/problems/happy-number/

     两数之和

    本题采用map因为：我们需要存放的是（元素，下标），因为存放两个值，所以不能用数组和set。

    思路：

    要找出两数之和是否等于目标值，可以利用哈希思想。

    在遍历数组时，对于当前遍历元素，通过target-目标元素=需要元素，再判断之前的map中是否存在了需要元素，如果没有，继续向前遍历，同时把目标元素插进map中。

    1. class Solution {
    2. public:
    3.     vector<int> twoSum(vector<int>& nums, int target) {
    4.         unordered_map<int, int>un_map;
    5.         for(int i = 0; i < nums.size(); i++){
    6.             int s = target - nums[i];
    7.             auto iter = un_map.find(s);//找到返回迭代器，否则返回跌倒器最后位置空
    8.             if(iter != un_map.end()){
    9.                 return {iter->second, i};
    10.             }
    11.             //没找到，把当前遍历元素插入map
    12.             un_map.insert(pair<int, int>(nums[i], i));
    13.         }
    14.         return {};
    15.     }
    16. };

    相关题目：

    1. 两数之和 - 力扣（LeetCode）https://leetcode.cn/problems/two-sum/

    四数相加Ⅱ

    本题的思想在于，把两个数组分成两部分，对第一部分求得一个和以及次数，第二部分也是如此，最后在遍历第二部分的时候，判断两部分的和是否相加为0，如果满足，就把第一部分该数的次数记录下来。

    1. class Solution {
    2. public:
    3.     int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    4.         unordered_map<int, int>un_map;
    5.         //统计1，2数组相加后的元素和以及次数
    6.         for(auto x : nums1){
    7.             for(auto y : nums2){
    8.                 un_map[x + y]++;
    9.             }
    10.         }
    11.         int count = 0;//统计x+y+z+w=0的次数
    12.         for(auto z : nums3){
    13.             for(auto w : nums4){
    14.                 if(un_map.find(0 - (z + w)) != un_map.end()){
    15.                     count += un_map[0 - (z + w)];
    16.                 }
    17.             }
    18.         }
    19.         return count;
    20.     }
    21. };

    相关题目：

    454. 四数相加 II - 力扣（LeetCode）https://leetcode.cn/problems/4sum-ii/

    三数之和

    本题利用双指针思路解决。a+b+c=0

    对原数组进行排序，这样方便我们比较结果是否=0，并且排序后的第一个元素如果>0，那么后面不用比较了。

    1.     vectorint>> ans;
    2.     sort(nums.begin(),nums.end());
    3.     //找到a+b+c=0，其中a固定位置，b为left，c为right
    4.     for(int i = 0; i < nums.size(); i++){
    5.         //如果起始位大于0，则不可能满足条件
    6.         if(nums[i] > 0){
    7.             return ans;
    8.         }
    9. }

    对a进行去重，这时我们需要判断a与a前面一个元素而不是a和a的后一个元素，因为会漏掉 -1 -1 2这种情况

    1.         //对a去重
    2.         if(i > 0 && nums[i] == nums[i - 1]){
    3.             continue;
    4.         }

    定义双指针，判断a+b+c的值和0的大小，大于就right左移，小于left右移，等于就把结果插入数组，并且指针移动

    1.          int left = i + 1;
    2.         int right = nums.size() - 1;
    3.         while(right > left){
    4.             //不用>= 是因为不满足求的三个元素，right不能是left
    5.             if(nums[i] + nums[left] + nums[right] > 0){
    6.                 right--;
    7.             }
    8.             else if(nums[i] + nums[left] + nums[right] < 0){
    9.                 left++;
    10.             }
    11.             else{
    12.                 //a+b+c=0了
    13.                 ans.push_back(vector<int>{nums[i],nums[left],nums[right]});
    14.                 right--;
    15.                 left++;
    16.         }

    对b，c去重

    1.                 //对b。c去重
    2.                 while(right > left && nums[right] == nums[right - 1]){
    3.                     right--;
    4.                 }
    5.                 while(right > left && nums[left] == nums[left + 1]){
    6.                     left++;
    7.                 }

    所有代码如下：

    1. class Solution {
    2. public:
    3.     vectorint>> threeSum(vector<int>& nums) {
    4.     vectorint>> ans;
    5.     sort(nums.begin(),nums.end());
    6.     //找到a+b+c=0，其中a固定位置，b为left，c为right
    7.     for(int i = 0; i < nums.size(); i++){
    8.         //如果起始位大于0，则不可能满足条件
    9.         if(nums[i] > 0){
    10.             return ans;
    11.         }
    12.         //对a去重
    13.         if(i > 0 && nums[i] == nums[i - 1]){
    14.             continue;
    15.         }
    16.         int left = i + 1;
    17.         int right = nums.size() - 1;
    18.         while(right > left){
    19.             //不用>= 是因为不满足求的三个元素，right不能是left
    20.             if(nums[i] + nums[left] + nums[right] > 0){
    21.                 right--;
    22.             }
    23.             else if(nums[i] + nums[left] + nums[right] < 0){
    24.                 left++;
    25.             }
    26.             else{
    27.                 //a+b+c=0了
    28.                 ans.push_back(vector<int>{nums[i],nums[left],nums[right]});
    29.                 //对b。c去重
    30.                 while(right > left && nums[right] == nums[right - 1]){
    31.                     right--;
    32.                 }
    33.                 while(right > left && nums[left] == nums[left + 1]){
    34.                     left++;
    35.                 }
    36.                 right--;
    37.                 left++;
    38.             }
    39.            
    40.         }
    41.     }
    42.      return ans;
    43.     }
    44. };

    相关题目：
    15. 三数之和 - 力扣（LeetCode）https://leetcode.cn/problems/3sum/

    四数之和

    本题采用三数之和思路，这里只讲一下不特点。

    除开双指针，多引入一个k，在i的前面，同时对k做和 i 做之前相同的剪纸和去重操作。

    1. for(int k = 0;k < nums.size(); k++){
    2.             //剪纸
    3.             if(nums[k] > target && nums[k] >= 0){
    4.                 break;
    5.             }
    6.             //对nums[k]去重
    7.             if(k > 0 && nums[k] == nums[k - 1]){
    8.                 continue;
    9.             }
    10. }

    整个代码如下：

    1. class Solution {
    2. public:
    3.     vectorint>> fourSum(vector<int>& nums, int target) {
    4.         vectorint>>ans;
    5.         sort(nums.begin(),nums.end());
    6.         for(int k = 0;k < nums.size(); k++){
    7.             //剪纸
    8.             if(nums[k] > target && nums[k] >= 0){
    9.                 break;
    10.             }
    11.             //对nums[k]去重
    12.             if(k > 0 && nums[k] == nums[k - 1]){
    13.                 continue;
    14.             }
    15.             for(int i = k + 1; i < nums.size(); i++){
    16.                 //剪纸
    17.                 if(nums[k] + nums[i] > target && nums[k] + nums[i] >= 0){
    18.                     break;
    19.                 }
    20.                 //对nums[i]去重
    21.                 if(i > k + 1 && nums[i] == nums[i - 1]){
    22.                     continue;
    23.                 }
    24.                 //双指针
    25.                 int left = i + 1;
    26.                 int right = nums.size() - 1;
    27.                 while(right > left){
    28.                     //对a++c+d和0关系判断
    29.                     if((long)nums[k] + nums[i] + nums[left] + nums[right] > target){
    30.                         right--;
    31.                     }
    32.                     else if((long)nums[k] + nums[i] + nums[left] + nums[right] < target){
    33.                         left++;
    34.                     }
    35.                     else{
    36.                         ans.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
    37.                         while(right > left && nums[right] == nums[right - 1]){
    38.                             right--;
    39.                         }
    40.                         while(right > left && nums[left] == nums[left + 1]){
    41.                             left++;
    42.                         }
    43.                         right--;
    44.                         left++;
    45.                     }
    46.                 }
    47.             }
    48.         }
    49.         return ans;
    50.     }
    51. };

    相关题目：

    18. 四数之和 - 力扣（LeetCode）https://leetcode.cn/problems/4sum/

  • 相关阅读:
    音视频发展调研
    百度测开面试题分享
    Selenium元素定位神器工具谷歌浏览器插件-SelectorsHub介绍、安装和使用
    什么是JWT?
    冷知识：Mysql最大列限制和行限制
    [WTL/Win32]_[中级]_[MVP架构在实际项目中的应用]
    docker 命令
    PaxCompiler语言的编译器
    前端表单滑块验证码开发
    CoDeSys系列-4、基于Ubuntu的codesys运行时扩展包搭建Profinet主从环境
  • 原文地址：https://blog.csdn.net/m0_60524373/article/details/126828411