您现在的位置是：首页 >技术教程 >代码随想录算法训练营第六天|242.有效的字母异位词 、349. 两个数组的交集 、202. 快乐数、1. 两数之和网站首页技术教程

哈希表的表示方式：数组、set、map
数组：范围可控的情况下，可以用数组
set：哈希值较大的情况下，或数值分布很分散的情况
map：key 和 value对应的情况下
能用数组尽量用数组，因为数组会比较快！set、map的结构更复杂，浪费时间多

有效的字母异位词

题目链接：力扣

解题思路：第一种，类似于暴力遍历；第二种巧用数组构成哈希表，由于题目所给的都是小写字母，所以可以构建一个大小为26的数组，对应着a~z，当字符串s中出现某一字符时，在数组相应位置++，当字符串t中出现某一字符时，在数组相应位置--；最后检查数组中各元素是否为0，若不为0，则说明不是有效的字母异位词

暴力解法：

    bool isAnagram1(string s, string t) {

        if(s.size() != t.size())
        return false;

        unordered_map<char,int> mymap;            //key是字符，int是出现次数
        for(int i=0; i<s.size();i++)            
        {
            if(mymap.find(s[i]) == mymap.end())   //不存在 则插入
                mymap[s[i]] = 1;
            else                                  //存在，则该key值数量++
                mymap[s[i]]++;                   
        }
        for(int j=0; j<t.size();j++)
        {
            if(mymap.find(t[j]) == mymap.end())    //没找到
                 return false;
            else
                {
                    mymap[t[j]]--;                 //找到则对应key值数量--
                    if(mymap[t[j]] <= 0)           //若数量小于等于0
                      mymap.erase(t[j]);           //则将该key值从map中删除
                }
        }
        return true;
    }

数组哈希法：

bool isAnagram(string s, string t) {
         
         int Mymap[26] = {0};

         for(int i=0;i<s.size();i++)
             Mymap[s[i]-'a']++;

         for(int j=0;j<t.size();j++)
             Mymap[t[j]-'a']--;
    
         for(int i=0;i<26;i++)
         {
             cout<<i<<":"<<Mymap[i]<<endl;
             if(Mymap[i]!=0)
              return false;
         }
         return true;

     }

时间复制度O(n)，空间复杂度O(1);

两个数组的交集

题目链接：力扣

知识点：哈希表最擅长的事情：给你一个元素，判断在某个集合中是否出现过。

解题思路：将num1转化为哈希表，将其所有放入哈希表中，再遍历num2的每一个元素是否在哈希表中出现过，若出现过，则最终放入result集合（result也是一个set，自带去重）中。最后将result转化为vector。
关于set的选择，这里采用unordered_set，因为其底层是哈希表（set和multiset底层是红黑树），其做映射的效率最高，做取值操作效率也最高。
代码如下：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> RES;
        unordered_set<int> N1(nums1.begin(),nums1.end()) ;

        for(int i=0;i<nums2.size();i++)
        {
            if(N1.find(nums2[i]) != N1.end())
                RES.insert(nums2[i]);
        }
        return vector<int>(RES.begin(),RES.end());
    }
};

快乐数

 题目链接：力扣

知识点：题目中提到，无限循环，也就是说求和的过程中，sum会重复出现 。
当快速判断一个元素是否出现集合里的时候，考虑哈希法。
这题还要掌握的是求和的过程。

附上我的代码，和卡哥思路类似：

 bool isHappy(int n) {
        
        int sum = 0;
        unordered_set<int> Res;
        Res.insert(n);
        while(1)
        {
            if(n == 1)
            return true;

             while(n)
            {
              int reminder = n % 10;
              sum += reminder * reminder;
              n = n/10;
            }

            if(Res.find(sum) == Res.end())  //没找到，不存在
             {
                 Res.insert(sum);
                 n = sum;  sum = 0;
             }
            else
             return false;

        }
     
     }

两数之和

题目链接：力扣

解题思路：将遍历过的元素加到集合里， 然后判断，我们想要寻找的元素是否在这个集合中出现过，若在这个集合里出现过，就是我们之前遍历过的。
同时我们还要知道这个元素出现的下标，即我们要存储两个元素，让数组做Key，下标做value，所以采用unordered_map。其中map用于存放遍历过的元素。

这道题，自己写的不太好，看完卡哥的解答，明晰了不少，下面贴上卡哥的代码：

class Solution {
public:
    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};
            }
            // 如果没找到匹配对，就把访问过的元素和下标加入到map中
            map.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
    }
};