哈希表 part01

今日任务
● 哈希表理论基础
● 242.有效的字母异位词
● 349. 两个数组的交集
● 202. 快乐数
● 1. 两数之和

链表理论基础

文章链接：https://programmercarl.com/哈希表理论基础.html#哈希表

重点：

1. 哈希表是根据关键码的值而直接进行访问的数据结构。

2. 一般哈希表都是用来快速判断一个元素是否出现集合里。

3. 哈希表的关键是哈希函数。哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。
   

4.哈希函数映射到数组的同一个下标可能会产生哈希碰撞。如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。

5.哈希碰撞可以用两种方法解决：第一是拉链法，冲突结点可以转换成链表结构存储。第二是线性检测法，需要有足够大的尺寸，让冲突结点存到其他地方去。

6.C++中的哈希表实现

Problem: 242. 有效的字母异位词

思路

首先我们因为字母是有限个，所以我们可以利用数组去存储。一共26个字母，所以数组大小为26，并且不用记住字母下标，只要计算与'a'的相对距离即可。遍历一遍数组a，遍历一遍数组b，最后我们通过查看结果数组即可判断是否是异位词。

解题方法

哈希表

Code

//时间复杂度: O(n)
//空间复杂度: O(1)


class Solution {
public:
  bool isAnagram(string s, string t) {
       int count[26] ={0};
       for(int i = 0; s[i] != '\0';i++){
          count[ (int)s[i]-'a']++;
       }
      for(int i = 0; t[i] != '\0';i++){
          count[ (int)t[i]-'a']--;
      }
      for(int i = 0; i < (sizeof (count) / sizeof (count[0]));i++){
          if(count[i] != 0) return false;
      }

      return true;
  }
};

Problem: 349. 两个数组的交集

思路

首先，用一个哈希表set去初始化第一个数组，用一个空哈希表专门保存结果数据，然后遍历第二个数组里的所有数字，如果有数字出现在哈希表中就插入结果哈希表中，最后返回这个结果哈希表。

解题方法

哈希表

Code

//时间复杂度: O(mn)
//空间复杂度: O(n)

class Solution {
public:
  vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
      unordered_set<int> res; // 存放结果，之所以用set是为了给结果集去重
      unordered_set<int> nums_set(nums1.begin(), nums1.end());

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

Problem: 202. 快乐数

思路

首先我们每求到一个数字的快乐数，先判断这个快乐数曾经在哈希表出现过，如果出现过，那么说明这个数的求快乐数的过程会进入死循环，永远求不到快乐数==1的情况，就立刻返回false。如果没出现过就将该结果插入哈希表。

解题方法

先判断是否重复，再插入，如果有重复直接返回false，快乐数==1退出循环。

Code

//时间复杂度: O(logn)
//空间复杂度: O(logn)


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> sum_res;
      while(1){
          int sum = getSum(n);
          if(sum == 1){
              return true;
          }

          if(sum_res.find(sum) != sum_res.end()){
              return false;
          }else{
              sum_res.insert(sum);
          }
          n = sum;
      }

  }
};

Problem: 1. 两数之和

思路

为什么会想到用哈希表？因为当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

哈希表为什么用map？因为我们问题要求我们返回的是下标。

本题map是用来存什么的？键存的是数值，方面find函数查找，值存的的下标，通过迭代器返回。

解题方法

哈希表

Code

/*
用unordered_map不是不能存储两个相同的key吗，那如果数组里两个出现相同的两个元素都要存储会怎么样呢？
注意它存入的方式，它是在循环的过程中边检验边存的，如果没有对应的数字就存入map，如果有就计数，这样不会遇到重复的
*/

//时间复杂度: O(n)
//空间复杂度: O(n)


class Solution {
public:
  vector<int> twoSum(vector<int>& nums, int target) {
      unordered_map<int, int> res;//创建一个map用来查找结果
      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 {}; 
  }
};

热门相关：你好，霍少大人   重生成偏执霍少的小仙女   精灵掌门人   精灵掌门人   上将大叔，狼来了！