哈希表理论基础

哈希表又称散列表，直白来讲就是数组

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。
比如：要查询一个名字是否在这所学校里面。
要枚举的话时间复杂度是O（n），但如果使用哈希表的话，只需要O（1）就可以做到。
我们只需要初始化把这所学校里学生的名字存在哈希表里，在查询的时候通过索引值直接就可以知道这位同学在不在这所学校里了。
将学生姓名映射到哈希表上就涉及到了hash functio，也就是哈希函数

哈希函数

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

哈希碰撞

如图所示：小李和小王都映射到了索引下标1的位置，这一现象叫做哈希碰撞

解决方法

1、拉链法：选择合适的哈希表大小，这样即不会因为数值空值而浪费大量内存，也不会因为链表太长而查找上浪费太多时间。
2、线性探测法：需要依靠哈希表中的空位来解决碰撞问题。
例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示：

常见的三种哈希结构

数组
set（集合）
map（映射）

总结：
当我们遇到要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。哈希法是牺牲空间换时间。

1、有效的字母异位词

题目：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。（字母异位数指的是两个字符串有相同的字符，但位置可以不同）
示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true
示例 2: 输入: s = “rat”, t = “car” 输出: false

力扣题目链接：https://leetcode.cn/problems/valid-anagram/
思路：https://www.bilibili.com/video/BV1YG411p7BA

思路：使用哈希表中的数组来解决，首先创建大小为26位的数组（因为26个字母，所以数组26大小够了），计数字符串s上的字符个数，再减去字符串t上的字符个数，最后再判断数组中的所有值是否为0。如果都是为0，说明字符串s加的数被字符串t所减去了。如果不都是为0，说明一个字符串肯定比另外一个子串多些字符。由此可以判断是否为有效字母异位数。

var isAnagram = function(s, t) {
    // 长度不同，说明它们不是字母异位词
    if(s.length != t.length) return false;

    let arr = new Array(26).fill(0); // 创建一个长度为26的数组，并用0填充
    let base = "a".charCodeAt(); // 获取a的ASCII码值

    // 计算字符串s 每个字符的数量
    for(let i of s){
        arr[i.charCodeAt() - base]++;
    }

    // 减去计算字符串t的数量
    for(let i of t){
        if(!arr[i.charCodeAt() - base]) return false;// 说明字符串t中出现了字符串s中的没有的字符
        arr[i.charCodeAt() - base]--;
    } 
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2、两个数组的交集

题目：给定两个数组，编写一个函数来计算它们的交集。

说明：输出结果中的每一个元素一定是唯一的。我们可以不考虑输出结果的顺序

力扣题目链接：https://leetcode.cn/problems/intersection-of-two-arrays/
思路：https://www.bilibili.com/video/BV1ba411S7wu

<script>
          var intersection = function (nums1, nums2) {
            // 方法一：使用双重循环，找到两个数组的交集，在使用set去重并转回数组类型
             /*   let result = [] 
               for(let i=0; i
                
               // 第二种方法 使用set求两数组交集
               let arrt = []; // 用于存放交集
               let arrt1 = new Set(nums1); // 转为set类型去重
               let arrt2 = new Set(nums2);
               
               // js中Array可以使用下标，Map和Set不能使用下标,使用forEach循环遍历
               arrt2.forEach((item) =>{
                   // set.has(value) 判断value是否在set中，返回值Boolean
                    arrt1.has(item) && arrt.push(item) // 简写 如果存在则添加到数组中
               })
               return arrt;
          };
          console.log(intersection([1, 2, 2, 1], [2, 2]))
     </script>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

3、快乐数

题目：编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False。

力扣题目链接：https://leetcode.cn/problems/happy-number/

思路：这道题的难点就是判断是否进入了循环，我这里的解题[[使用的是Map（），把每次的求和结果存到Map结构中，然后判断求和结果是否有出现过，如果有出现，代表进入了循环，就return false。

var getSum = function(n){
     sum = 0;
    while(n){
        sum += Math.pow(n%10,2); // 求平方
        // 注意：JS除法得到的是小数，Java中的除法得到的整数
        n = Math.floor(n/10); // Math.fllor()向下取整 比如 1.56 向下取整变成1
    }
    return sum;
}

var isHappy = function(n) {
  // 创建Map类型
  let map = new Map();

  while(true){
      if(map.has(n)) return false; // 如何map中存在求和返回过来的值说明进入了死循环
      if(n == 1) return true; // 说明这个数是快乐数
      map.set(n,1); // 把每一次求和的结果保存到map中，以便后面查询是否出现重复
      n = getSum(n); // 各数字平方求和
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4、两数之和

题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

力扣题目链接：https://leetcode.cn/problems/two-sum/
思路：https://www.bilibili.com/video/BV1aT41177mK

思路：需要使用key value解构来存放，key来存放元素，value来存放下标，那么使用map正合适

var twoSum = function(nums, target) {
    let has = {};
    for(let i=0; i<nums.length; i++){
        // 如果另外一个整数的下标不等于undefined，那么说明找到了，则就返回两个整数的下标
        if(has[target-nums[i]] != undefined){ 
            return [i,has[target-nums[i]]]
        }
        has[nums[i]] = i; // has采用键值对的形式来存储，键名存放的是nums的值，键值存放的是nums数据的下标
    }
};
1
2
3
4
5
6
7
8
9
10

5、四数相加II

题目：给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

力扣上的题目链接：https://leetcode.cn/problems/4sum-ii/
思路：https://www.bilibili.com/video/BV1Md4y1Q7Yh

思路：这里我使用的是Map结构来做的，四和运算我们可以看成是两和运算。我们先遍历前两个数组的数据，存放到Map结构中，在用0减去后两个数组遍历数据的求和，去Map中找，是否存在该数据，如果存在，则计数。

var fourSumCount = function(nums1, nums2, nums3, nums4) {
    // 使用map集合来解决
    let map = new Map();
    count = 0; // 求和

    // 遍历前面2个数组中的数据求和 存放到map中
    for(let i of nums1){
        for(let j of nums2){
            let sum = i+j; // 求和
            map.set(sum,(map.get(sum) || 0)+1); // 把求和的数存到map中的键名，相同求和个数存放到键值中
        }
    }

    // 遍历后面2个数组中的数据求和 去map中找，是否存在
    for(let i of nums3){
        for(let j of nums4){
             // 就好像把（num1[i]+num2[j]）看作一个整体a表示，（num3[i]+num4[j]）看作一个整体b表示，它两相加要等于0，所以b就可以用0-a来使得a+b=0
            let sum = 0-(i+j);
            // map.get返回是键所映对的值
            count += map.get(sum) || 0;// 如果存在，则count加上键值，因为如果前面有三个求和一样，加上后面这个sum等于0，就代表着有三种方法相加求和为0
        }
    }
    return count
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

6、赎金信

题目：给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

力扣题目链接：https://leetcode.cn/problems/ransom-note/

思路：使用数组，把magazine的字符串，利用数组下标存放起来，之后在循环ransom中的字符串也是利用数组下标去做相应的减法，如果找到的那个下标为0说明就是magazines没有ransom的字符，或者ransom中的某些重复的字符比较多，magazine不能一一对应。

// 判断 ransomNote中的所有字符是否可以在magazine中全部找到，跟有效字符的异位词差不多，但这个是针对于两个数组，都有相同的字符，字符位置不做强求
var canConstruct = function(ransomNote, magazine) {
   // 使用数组解决
   let arr = new Array(26).fill(0); // 创建大小位26位的数组，并且填充为0
   let base = 'a'.charCodeAt(); // 获取字符a的ASCII

   for(let i of magazine){ // 利用数组的下标来存储字符串的个数，比如“abb” 那么字符a的下标为a-a=0，并且arr[0]为1，代表字符a只有一个
       arr[i.charCodeAt()-base]++;
   }
   for(let i of ransomNote){
       if(!arr[i.charCodeAt()-base]) return false;
       arr[i.charCodeAt()-base]--;
   }
   return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15