常见的三种哈希结构

• 数组

• set （集合）

• map(映射)

1.数组：

当题目限制了数组的大小时可以使用，如果哈希值较大跨度大会造成数组空间的浪费

2.set:

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

set和map的区别，

1. Map是键值对，Set是值的集合，当然键和值可以是任何类型的值；

2. Map可以通过get方法获取值，而set不能因为它只有值；

3. 都能通过迭代器进行for...of遍历；

4. Set的值是唯一的可以做数组去重，Map由于没有格式限制，可以做数据存储

5. map和set都是stl中的关联容器，map以键值对的形式存储，key=value组成pair，是一组映射关系。set只有值，可以认为只有一个数据，并且set中元素不可以重复且自动排序。

3.map容器

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

1.迭代器访问

for (map<int,int>::iterator iter1=mp1.begin();iter1!=mp1.end();iter1++)

    { cout<<iter1->first<<endl;

}

2.auto自动访问

for (auto &iter1 : mp1)
        {cout<<iter1.first<<endl;//非指针类型

}

242.有效的字母异位词

1.数组：定义长度为26的一个hash数组，统计第一个字符串每一个的字母出现的频率，然后遍历第二个字符串，每个字母出现的频率对应做减法,最后判断hash数组是否为0。

class Solution {
public:
    bool isAnagram(string s, string t) {
       vector<int>hash(26,0);
       for(int i=0;i<s.size();i++)
       {
           hash[s[i]-'a']++;
       }
        for(int i=0;i<t.size();i++)
       {
           hash[t[i]-'a']--;
       }
        for(int i=0;i<26;i++)
       {
          
         if(hash[i]!=0)return false;
       }
       return true;
}
};

2.map容器

class Solution {
public:
    bool isAnagram(string s, string t) {
        map<int,int>mp1;
        map<int,int>mp2;
        for(int i=0;i<s.length();i++)
        {
            mp1[s[i]-'0']++;
        }
          for(int i=0;i<t.length();i++)//存ASII码
        {
            mp2[t[i]-'0']++;
        }
        if(mp1.size()!=mp2.size())return false;
        //
      for (map<int,int>::iterator iter1=mp1.begin();iter1!=mp1.end();iter1++)
    {  
            auto iter2=mp2.find(iter1->first);
            if(iter2==mp2.end())
            {
                return false;
            }
            else
            {
                if(iter1->second!=iter2->second)
                {
                    return false;
                }
            }
        }
        /
     for (auto &iter1 : mp1)
        {
        auto iter2 = mp2.find(iter1.first);
        if (iter2 == mp2.end())
        {
             return false;
        }
        else
        {
            if (iter1.second != iter2->second)
            {
               return false;
            }
        }
    }
       return true;
    }
};

相关题目

• 383.赎金信(opens new window)

• 49.字母异位词分组

• 438.找到字符串中所有字母异位词

349. 两个数组的交集

用set容器，降重。可以相互复制vector元素与set元素

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
  unordered_set<int>set1;
  unordered_set<int>nums_set(nums1.begin(),nums1.end());//将vector数组的元素复制到set
   for(int num:nums2)
   {
       if(nums_set.find(num)!=nums_set.end())// 发现nums2的元素 在nums_set里又出现过就存在set1中
       {
           set1.insert(num);
       }
   }
   vector<int>result(set1.begin(),set1.end());//从set复制元素到vector数组
  return result;
    }
};

202.快乐数

思路：sum会重复出现就进入死循环了，用set存sum值，查找到相同的就返回false

class Solution {
public:
  int getsum(int n)
  {
    int sum=0;
    while(n)
        {
            sum+=(n%10)*(n%10);
            n=n/10;
        }
  return sum;
  }
    bool isHappy(int n) {
        unordered_set<int>settable;
      
        while(1)
        {
          int m=getsum(n);
          if(m==1) return true;
          if(settable.find(m)!=settable.end())
          {
              return false;
          }
           settable.insert(m);
           n=m;
        }
        return true;
    }
};

1. 两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        multimap<int,int>mp;
        vector<int>result;
        for(int i=0;i<nums.size();i++)
        {
            mp.insert(pair<int,int>(nums[i],i));
        }
        for(auto &itt:mp)
    {     cout<<itt.first<<" "<<itt.second<<endl;}
    for(auto &it:mp)
    {      auto iter=mp.find(target-it.first);
        if(*iter!=it&&iter!=mp.end())
        {
           result.push_back(it.second);
           result.push_back(iter->second);
           break;
        }
    }
        return result;
    }
};