代码随想录day5--哈希表基础

理论基础

在解题之前，需要明白什么是哈希表，很多同学对哈希表的了解可能不是很多，只是停留在书本上介绍的至少。用大白话来解释哈希表，哈希表中的关键码就是数值的索引下标，然后通过下标直接访问数组中的元素，如下表所示：

这时候就有同学要问了，那么哈希表到底是解决什么问题的，一般哈希表是用来快速判断一个元素是否出现在集合里的。

例如要查询一个名字是否在这所学校里，如果使用枚举的时间复杂度是O(n)，但如果使用哈希表的话，只需要O(1)就可以做到。我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学是否存在。

将学生姓名映射到哈希表上就涉及到了hash function，也就是哈希函数了

---

哈希函数

哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

通过hashCode把名字转化为数值，一般hasdCode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

所以可以得出以下：

index = hashFunction(name);hashFunction = hasCode(name)%tableSize;

这里的hashCode一定要取模，因为hashCode可能大于tableSize（哈希表长度），为了确保所有索引数据都在哈希表上，所以要取模。

但是如果要存的数据大于哈希表长度，此事就算哈希函数计算的再均匀，也避免不了有两个甚至多个数据映射到哈希表同一个索引下标位置。这就会产生哈希碰撞。

---

哈希碰撞

哈希碰撞也就是大家在学数据结构的过程中，着重学习的方法，分为：拉链法和线性探测法。

1）线性探测法，冲突发生，顺序查看表中的下一个元素，直到找出一个空闲单元

2）平方探测法：设发生冲突的地址为d，平方探测法得到的新的地址序列为：d+1^2，d-1^2，d+2^2，d-2^2。由于大家在学习数据结构时学习过，所以这里就不着重讲述了。

---

常见的三种哈希结构

当我们像啊哟使用哈希法来解决问题的时候，我们一般会选择以下三种数据结构：

·数组

·set（集合）

·map（映射）

数组是我们平时用的最多了，而且用法比较简单，所以就不过多赘述。

在C++中，set和map分别提供以下三种数据结构，其底层实现以及优劣如下表：

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

std::unordered_set底层实现为哈希表，std::set和std::multiset的地城实现是红黑树，红黑树是一种

平衡二叉搜索树，所以key值是有序的，但key不可以改变，改动key值会导致整棵树的错乱，所以只能删除和增加。

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

std::unordered_map底层实现为哈希表，std::map和std::multimap的底层实现是红黑树。同理，std::map和std::multimap的key也是有序的。

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

接下来看map，在map是一个key value的数据结构，map中，对key是由限制，对value没有限制的，因为key的存储方式是使用红黑树实现的。

---

总结

当我们遇到要快速判断一个元素是都出现集合里的时候，就要考虑哈希法。

但是哈希法就是牺牲空间换取时间，因为要使用额外的数组，set或者map来存放数据，才能实现快速的查找。所以大家在做题目的时候遇到需要判断一个元素是否出现的场景也应该第一时间想到哈希法。

---

LeetCode242.有效的字母异位词

题目描述：

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

解题思路：

·题中说字符串只有小写字符，那么只需要定义一个数组，用于记录字符串s中字符出现的次数。

定义一个长度为26的数组，因为字符a~z的ASCII也是26个连续的数值。

·在遍历第一个字符串时，将s[i]-'a'所在的元素+1即可，在遍历第二个字符串时，将s[i]-'a'所在的元素-1即可。

·最后检查一下，数组中，如果又元素不等于0，说明字符串1和字符串2一定有多了字符，或者少了字符，那么就是无效的字母异位词。

代码如下：

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};//初始化数组
        for(int i = 0;i < s.size();i++){//遍历第一个字符串
            record[s[i] - 'a']++;
        }
        for(int i = 0;i < t.size();i++){//遍历第二个字符串
            record[t[i]-'a']--;
        }
        for(int i = 0;i < 26;i++){//如果存在不等于零的数值直接返回0，说明是无效的字母异位词
            if(record[i] != 0){
                return false;
            }
        }
        return true;
    }
};

总结：这道题主要是带我们了解了哈希表的基本用法之一，代码与理解上并没有什么难点

---

LeetCode349.两个数组的交集

题目描述：

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

解题思路：

·看完题目后第一个想法是使用类似上一题一样的解法进行求解，但是在得处结果后，需要增加去重步骤

·根据去重这一步，我又想到了可以使用哈希表中的set进行求解，而且不需要去重（因为set自带去重功能）

使用set解题代码如下：

class Solution {
public:
    vector intersection(vector& nums1, vector& nums2) {
        unordered_set result_set;//存放结果，并且使用set进行去重
        unordered_set nums_set(nums1.begin(),nums1.end());//将num1数组中的数据从头到尾传递到nums_set中
        for(int num : nums2){//遍历nums2中的每个元素
            if(nums_set.find(num) != nums_set.end()){
                result_set.insert(num);
            }
        }
        return vector(result_set.begin(),result_set.end());//结果输出数组，与顺序无关
    }
};

·时间复杂度：O(n+m) m是因为最后要把set转化成vetor

·空间复杂度：O(n)

易错点：

·关于set，C++提供了三种可用数据结构，在文章开始我们已经讲解，其中使用unordered_set读写的效率是最高的，不需要对数据进行排序，而且可以去重，所以我们选择unordered_set。

·还有需要注意的一点，set占用的空间比数组大，而且速度比数组慢，set把数值映射到key上都要做hash计算。

使用数值解题代码如下：

class Solution {
public:
    vector intersection(vector& nums1, vector& nums2) {
        unordered_set result_set;//使用set进行去重
        int hash[1005] = {0};//默认数值为0
        for(int num : nums1){//在nums1中出现的字母在hash数值中做记录
            hash[num] = 1;
        }
        for(int num:nums2){//在nums2中出现，result记录
            if(hash[num] == 1){
                 result_set.insert(num);
            }
        }
        return vector(result_set.begin(),result_set.end());
    }
};

·时间复杂度：O(m+n)

·空间复杂度：O(n)

易错点：

使用数组进行哈希的题目求解，只能在题目限制了数值大小的前提下进行求解，如若题目没有限制数值的大小，就无法使用数组来做哈希表了。而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费， 所以这种情况就需要使用set。

---

LeetCode202.快乐数

题目描述：

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

  如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

  示例 1：

  输入：n = 19
  输出：true
  解释：
  12 + 92 = 82
  82 + 22 = 68
  62 + 82 = 100
  12 + 02 + 02 = 1
  

  示例 2：

  输入：n = 2
  输出：false

  解题思路：

  ·题目中说了会出现无限循环，所以说明在求和过程中，sum会重复出现。正如我们之前说的，要快速判断一个元素是否出现在集合里是，就可以考了哈希法。

  代码如下：

  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 set;
          while(1){
              int sum = getSum(n);
              if(sum == 1) return true;
          if(set.find(sum) != set.end()){//判断sum是否出现，若出现则直接结束循环
              return false;
          }else{
              set.insert(sum);
          }
          n = sum;
          }
      }
  };

  ·时间复杂度：O(logn)

  ·空间复杂度：O(logn)

  总结：

  在解题过程中，需要透过题目看到题解的本质，这样就会轻松的找到其中的解题方法，从而可以轻松的解题。

  ---

  LeetCode1.两数之和

  题目描述：

  给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

  你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

  你可以按任意顺序返回答案。

  示例 1：

  输入：nums = [2,7,11,15], target = 9
  输出：[0,1]
  解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
  

  示例 2：

  输入：nums = [3,2,4], target = 6
  输出：[1,2]
  

  示例 3：

  输入：nums = [3,3], target = 6
  输出：[0,1]

  解题思路：

  ·使用暴力法，可以很轻松的解决，我们就不过多赘述了

  ·题目说，需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想打哈希法。本题呢，就需要一个集合来存放我们遍历过的元素，然后再遍历数组的时候去访问这个集合，某元素是否遍历过，也就是是否会出现在这个集合，那么我们就应该想到哈希法。

  ·因为本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用key value结构来存放，key保存元素，value保存下标，所以选择map正合适。

  代码如下：

  class Solution {
  public:
      vector twoSum(vector& nums, int target) {
          std::unordered_map  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(nums[i], i)); 
          }
          return {};
      }
  };

  ·时间复杂度：O(n)

  ·空间复杂度：O(n)

  难点：

  ·数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。

  ·set是一个集合，里面存放的元素只能是一个key，而这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要放回x和y的下标，所以set不能使用。

  ·所以我们选择使用map，map可以使用key保存数值，用value再保存数值所在的下标。

  总结：

  需要明白一下四点：

  1.为什么会想到使用哈希表

  2.这道题为什么使用map

  3.map是用来存什么的

  4.map中的key和value分别用于存什么的