哈希表

哈希表理论基础

哈希表（英文名字为 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🔥Hot100

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

思路

可以利用 target-当前数，得到 map 中已经记录过的数字

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const map = new Map()
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i]
    if (map.has(target - num)) {
      return [map.get(target - num), i]
    } else {
      map.set(num, i)
    }
  }
}

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
}

5. 字母异位词分组

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

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释：

• 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
• 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
• 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = ["a"]

输出: [["a"]]

注：strs[i] 仅包含小写字母

思路

哈希表存储的 key 为字母异位词，value 为对应的满足条件的字符串数组

同时还要知道 key 是按 Unicode 字符排序后的字符串为键，
所以可以通过`strs[i].split('').sort().join('')`进行排序后形成 key

代码

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  const map = new Map()
  for (let i = 0; i < strs.length; i++) {
    const key = strs[i].split('').sort().join('')
    if (map.has(key)) {
      const arr = map.get(key)
      map.set(key, [...arr, strs[i]])
    } else {
      map.set(key, [strs[i]])
    }
  }
  const result = []
  map.forEach((value, key) => {
    result.push(value)
  })
  return result
}

6. 最长连续序列

🔗力扣题目链接https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envI...🔥Hot100

给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]

输出：4

解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]

输出：9

示例 3：

输入：nums = [1,0,1,2]

输出：3

思路

1. 将数组转换为 Set 来存储哈希内容，实现去重和 O(1) 查找
2. 如何找到开始数字：只有当 num-1 不存在时，才说明 num 是一个序列的起点
3. 找到序列的长度：从当前数字开始，不断向上扩展序列即可

算法执行流程示例
以 `nums = [100, 4, 200, 1, 3, 2]` 为例：

1. 创建 `numSet = {100, 4, 200, 1, 3, 2}`
2. 遍历集合中的元素：
   - `num = 100`: 检查 `99` 是否存在 → 不存在 → 是起点 → 序列 [100]，长度 1
   - `num = 4`: 检查 `3` 是否存在 → 存在 → 不是起点 → 跳过
   - `num = 200`: 检查 `199` 是否存在 → 不存在 → 是起点 → 序列 [200]，长度 1
   - `num = 1`: 检查 `0` 是否存在 → 不存在 → 是起点 →
     - 从 1 开始向上扩展：1→2→3→4
     - 序列 [1,2,3,4]，长度 4
   - `num = 3`: 检查 `2` 是否存在 → 存在 → 不是起点 → 跳过
   - `num = 2`: 检查 `1` 是否存在 → 存在 → 不是起点 → 跳过
3. 最终结果：最长连续序列长度为 4

代码

var longestConsecutive = function (nums) {
  const numSet = new Set(nums)
  let longestStreak = 0

  for (const num of numSet) {
    // 只有当 num-1 不存在时，才说明 num 是一个序列的起点
    if (!numSet.has(num - 1)) {
      let currentNum = num
      let currentStreak = 1

      // 向上扩展序列
      while (numSet.has(currentNum + 1)) {
        currentNum++
        currentStreak++
      }

      longestStreak = Math.max(longestStreak, currentStreak)
    }
  }

  return longestStreak
}