哈希表常见例题

目录

一、哈希表的特点

二、使用情况

三、例题分析

1.有效的字母异位词

2.349数组交集

3.快乐数

4.两数之和

5.四数相加

总结

---

一、哈希表的特点

1.哈希表有键值对的机制，可通过查询key得到value

2.哈希表使用哈希函数得到索引，查询效率几乎为O1

3.unordered_set只有key且对放入其中的数据自动排序；

二、使用情况

当我们需要快速的知道某个元素之前是否出现过，可用哈希表进行存储。

三、例题分析

1.有效的字母异位词

思路：统计两个串中字母的数量，这个题可以用哈希表区统计数量但是没必要，我们直接用数组，厄里斯与桶的方式，创建26个桶去统计数量，第一个字母添加，第二个减少，如果桶中还有元素或者变成负值了，那就是不一样。

这种利用桶的方式统计数量，很常用，但是如果数据比较松散，数据量较大就不太适合。

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

相关题目 力扣383

2.349数组交集

思路：找两个数组的交集且不重复，也就是在遍历数组2的时候查询1中是否出现过我们可以用unordered_set，去重又能记录，然后用set做结果集

3.快乐数

思路：分解每一位算出平方和，记录，如果查到之前纪录过，那么不是，如果变为1则是

1.  
   class Solution {
2.  
   public:
3.  
   int squ(int num)
4.  
   {
5.  
   int sum=0;
6.  
   while(num)
7.  
   {
8.  
   sum =pow(num%10,2);
9.  
   num=num/10;
10.  
    }
11.  
    return sum;
12.  
    }
13.  
    bool isHappy(int n)
14.  
    {
15.  
    unordered_set<int>unset;
16.  
    int val=n;
17.  
    while(val!=1)
18.  
    {
19.  
    val=squ(val);
20.  
    if(unset.find(val)==unset.end())
21.  
    {
22.  
    unset.insert(val);
23.  
    }
24.  
    else
25.  
    {
26.  
    return false;
27.  
    }
28.  
    }
29.  
    return true;
30.  
    }
31.  
    };

4.两数之和

思路：这题如果是有序数组，那么可以用双指针做法，但这题无序，那么根据题意，我们只需要记录数组1中的值，然后遍历数组2查询是否存在target-num2【i】

1.  
   class Solution {
2.  
   public:
3.  
   vector<int> twoSum(vector<int>& nums, int target)
4.  
   {
5.  
   unordered_map<int,int>unmap;
6.  
   vector<int>vec;
7.  
   for(int i=0;i<nums.size(); i)
8.  
   {
9.  
   if(unmap.find(target-nums[i])!=unmap.end())
10.  
    {
11.  
    vec.push_back(unmap[target-nums[i]]);
12.  
    vec.push_back(i);
13.  
    }
14.  
    if(unmap.find(nums[i])==unmap.end())
15.  
    {
16.  
    unmap[nums[i]]=i;
17.  
    }
18.  
    }
19.  
    return vec;
20.  
    }
21.  
    };

5.四数相加

思路：本题对ijkl并没有什么限制，而且只求个数不用去重，那么我们可以计算出两个数字的和用哈希表存储，然后便俩后两个并查询-num3[i]-nums[j]是否存在

1.  
   class Solution {
2.  
   public:
3.  
   int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4)
4.  
   {
5.  
   unordered_map<int,int>unmap;
6.  
   int ans=0;
7.  
   for(int i=0;i<nums1.size(); i)
8.  
   {
9.  
   for(int j=0;j<nums2.size(); j)
10.  
    {
11.  
    unmap[nums1[i] nums2[j]];
12.  
    }
13.  
    }
14.  
     
15.  
    for(int i=0;i<nums3.size(); i)
16.  
    {
17.  
    for(int j=0;j<nums4.size(); j)
18.  
    {
19.  
    if(unmap.find(0-nums3[i]-nums4[j])!=unmap.end())
20.  
    {
21.  
    ans =unmap[0-nums3[i]-nums4[j]];
22.  
    }
23.  
    }
24.  
    }
25.  
    return ans;
26.  
    }
27.  
    };

这篇好文章是转载于：学新通技术网