哈希表

哈希表理论基础

哈希表（英文名字为 Hash table，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指 hash table 就可以了）。

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

这么官方的解释可能有点懵，其实直白来讲其实数组就是一张哈希表。

哈希表中关键码就是对象的 key，然后通过 key 直接访问对象中的值 obj[key]。(js 中 Object 和 Map 都可以表示)

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

例如：要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是 O(n)，但如果使用哈希表的话， 只需要 O(1)就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！

1. 两数之和 【简单】

🔗力扣题目链接https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked

给定一个整数数组 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]

2. 有效的字母异位词 【简单】

🔗力扣题目链接https://leetcode.cn/problems/valid-anagram/

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

示例 1:

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

输出: true

示例 2:

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

输出: false

思路

思路：

1. 先通过 `map` 存储 s 字符出现的次数
2. 遍历 t 中的每一个字符，去 map 中找是否有对应的，如果有，数量就-1，没有就返回 false

代码1

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
  if (s.length !== t.length) return false
  const map = {}
  for (let i = 0; i < s.length; i++) {
    const char = s[i]
    // 判断当前map是否有值，如果有数量就+1
    if (!map[char]) {
      map[char] = 1
    } else {
      map[char] += 1
    }
  }

  let flag = true

  for (let i = 0; i < t.length; i++) {
    const tChar = t[i]
    if (map[tChar] && map[tChar] > 0) {
      map[tChar]--
    } else {
      flag = false
    }
  }
  return flag
}

代码2

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
  if (s.length !== t.length) return false
  const map = new Map()
  // 统计s中每个字符的出现次数
  for (const char of s) {
    map.set(char, (map.get(char) || 0) + 1)
  }
  // 检查t中的字符是否与s完全匹配
  for (const char of t) {
    const count = map.get(char)
    if (!count) return false
    map.set(char, count - 1)
  }
  return true
}

3. 两个数组的交集 【简单】

🔗力扣题目链接https://leetcode.cn/problems/intersection-of-two-arrays/

给定两个数组 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] 也是可通过的

思路

> 使用 hash 表

## 代码 1

1. 去重：题目中说到**唯一**，那首先就是去重（后面说到 nums1、nums2 都是去重后的）
2. 获取到 nums1 的 map 结构，因为 map 结构可以让查找元素的时间复杂度最低
3. 遍历 nums2 的每一个元素，如果在 nums1 的 map 中，就 push 到 result 数组
4. 最后将这个 result 返回即可

## 代码 2

1. 对 nums1 去重
2. 定义一个 Set 结构(resultSet)，遍历 nums2，如果 nums2 中的元素在 nums1 的 Set 中，就往 resultSet 中添加（因为 Set 结构本来就会去重）
3. 最后将这个 resultSet 转为数组并返回

代码1

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  // 去重
  const uniqueNum1 = [...new Set(nums1)]
  const uniqueNum2 = [...new Set(nums2)]
  // 找交集，只需要遍历一个就行
  const map = {}
  for (let i = 0; i < uniqueNum1.length; i++) {
    const num = uniqueNum1[i]
    if (!map[num]) {
      map[num] = 1
    }
  }

  let result = []
  for (let i = 0; i < uniqueNum2.length; i++) {
    const num2 = uniqueNum2[i]
    if (map[num2]) {
      result.push(num2)
    }
  }

  return result
}

代码2

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  const resultSet = new Set()
  const num1Set = new Set(nums1)

  for (let i = 0; i < nums2.length; i++) {
    const num2 = nums2[i]
    if (num1Set.has(num2)) {
      resultSet.add(num2)
    }
  }

  return [...resultSet]
}

4. 快乐数 【简单】

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

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

「快乐数」定义为：

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

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

示例 1：

输入：n = 19

输出：true

解释：

1² + 9² = 82

8² + 2² = 68

6² + 8² = 100

1² + 0² + 0² = 1

示例 2：

输入：n = 2 输出：false

思路

1. 题中说可能是 **无限循环**，如果是无限循环那就应该退出，所以可以采用 `哈希表` 来判断这个数是否已经出现过，如果已经出现过就返回 `false`
2. 需要去循环，如果最后的结果是 `1` 或者在哈希表中有重复的，就结束循环
3. 最后判断是否等于 1，判断 true or false

代码

// 判断是否是快乐数
function isHappy(n) {
  // set、map、obj结构都可以是哈希表
  // 存放平方累加结果
  const sumSet = new Set()
  // 循环条件：sumSet只要重复出现了，就会进入死循环，就结构while
  while (n !== 1 && !sumSet.has(n)) {
    sumSet.add(n)
    n = getN(n)
  }
  return n === 1
}

function getN(num) {
  // 平方累加结果
  let res = 0
  while (num) {
    // 当前末尾数的平方
    const oneNum = (num % 10) * (num % 10)
    res += oneNum
    num = parseInt(num / 10)
  }
  return res
}