代码随想录算法训练营第六天|242 有效的字母异位词、349 两个数组的交集、202 快乐数、1 两数之和

哈希表理论基础

哈希表，也叫散列表，是根据key value而直接进行访问的数据结构。它把key value通过散列函数（哈希函数）映射到表中一个位置来访问。
接下来列举一个场景：

1. 如果要在学校找一个名叫大锤的学生，一般思路是把全校的学生名单拿出来，一个一个的查找，这种方法就是普通的顺序查找，依赖的是姓名的比较。但是如果拟恰巧遇见了一个大锤班里的同学张三，他就直接可以带你去找到大锤同学，这也就是说，只需要通过某个函数f(张三)，使得：

f(张三)=存储位置(大锤)

通过对key的映射，找到val在数组中索引，就可以O(1)的复杂度快速找到元素。

哈希碰撞

所有的key组成了输入空间，哈希表的索引组成了输出空间，输入空间是大于输出空间的。所以经过哈希函数映射后，就是说不同的key对应到了同一个索引。解决方法：

1. 拉链法，将发生冲突的元素都存储在链表中
2. 线性探测法，依次存放

常见的三种哈希结构

1. 数组
2. set
3. map

set

map

根据代码随想录中的总结：什么时候要使用哈希表呢？当我们要快速判断一个元素是否出现在集合里的时候，就要考虑哈希法。

242 有效的字母异位词

题目链接：有效的字母异位词

思路

暴力解法

若两个字符串为字母异位词，则两个字符串中的字母种类相同且个数相同，因此可以对两个字符串进行排序，如果排序后相同，则为异位词。

class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());

        if(s==t){
            return true;
        }
        return false;

   }
};

哈希表解法

那我们可以首先统计s中每个字符出现的次数，然后统计t中每个字符出现的次数，再看两个相不相等。再进一步考虑，使用什么来存储字符出现的次数，可以使用数组。然后呢，比如说字母a对应数组的哪一个索引，这样我们才能在字母a出现时在数组中的对应位置元素+1。可以使用哈希的思想，对每个字母-'a'就可以找到唯一的索引。
我们也不需要同时对s和t做统计，先对s做字母计数统计，然后对s做统计时，对应位置--。如果最后数组中的每个元素都为0，则s和t是异位词。

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

349 两个数组的交集

题目链接：两个数组的交集

思路

一个比较自然的想法，先统计nums1中的元素，去重后存起来记为A。然后遍历nums[2]中的元素，看其是否在A中，如果在A中，则就是要返回的元素。然后一个粗糙的解法如下：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> result;
        set<int> result1;
        for(int i=0; i<nums1.size();i++){
            if(find(result.begin(),result.end(), nums1[i]) == result.end()){
                result.insert(nums1[i]);
            }
        }
        for(int j=0; j<nums2.size(); j++){
            if(find(result.begin(), result.end(), nums2[j]) != result.end()){
                result1.insert(nums2[j]);
            }
        }
        return vector<int>{result1.begin(),result1.end()};

   }
};

还有一个更nice的写法：

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

        for(int num:nums2){
            if(result1.find(num) != result1.end()){
                result2.insert(num);
            }
        }
        return vector<int>(result2.begin(), result2.end());
  }
};

有以下几个有点：

1. set的底层是红黑树，查询和增删是O(logn)，而unordered_set的底层是哈系数，查询和增删是O(1)
2. 容器的初始化，可以使用begin和end的这种方式对一个容器进行初始化
3. 标准库算法find，可以直接通过容器.find()来查找元素

202 快乐数

题目链接：快乐数

思路

这道题目正常模拟就可以了，但是有很重要的一点是：如果开始循环重复则肯定不是快乐数，返回false。那么用unordered_set来存储每次的结果，如果有哪一次出现在了unordered_set中，则直接返回false。

class Solution {
public:
    int getSum(int n){
        int sum = 0;
        while(n){
            sum += (n%10) * (n%10);
            n /= 10;
        }
        return sum;
    }
    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 两数之和

题目链接：两数之和

思路

1. 两数之和，梦开始的地方
2. 有人夜里看海，有人leetcode第一题做不出来
3. 。。。。

暴力解法

遍历，两个for循环解决问题。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i=0; i<nums.size();i++){
            for(int j=i+1; j<nums.size();j++){
                if(nums[i]+nums[j] == target){
                    return {i,j};
                }
            }
        }
        return {};
  }
};

哈希法

在数组中找两个元素，其和等于target。我们使用一个for循环遍历每一个元素，把a + b = target转换为b = target - a。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> res;
        for(int i=0; i<nums.size(); i++){
            auto iter = res.find(target-nums[i]);
            if(iter != res.end()){
                return {iter->second, i};
            }
            else{
                res.insert(pair<int,int>(nums[i],i));
            }
        }
        return {};
  }
};

参考链接

1. https://www.jianshu.com/p/039e52defe16
2. 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%E5%87%BD%E6%95%B0