09 · 哈希表进阶

目标：用 Map / Set 做分组与 O(1) 查找；掌握异位词、连续序列套路。
精讲 49、128、242。

1. 为什么面试考

• 哈希表是 JS 刷题基本功（Map、Set、对象计数）。
• 异位词分组 考「设计 key」；最长连续序列 考 Set + 只从起点扩展。
• 前端一面常把 242 当热身，49 / 128 当区分度题。

2. 零基础概念

2.1 哈希表干什么

结构	典型用途
Map	键 → 值；分组、计数、存下标
Set	只关心「有没有」；去重、O(1) 查存在

2.2 设计 key 的两种方式

方法	适用
排序后的字符串	异位词："eat" → "aet"
26 位字母计数编码	异位词：避免排序，O(n) 建 key
数字本身	连续序列：直接在 Set 里找 num±1

2.3 最长连续序列的坑

❌ 对每个数都往左右扫 → O(n²)
✅ 只对 连续段起点（num-1 不在 Set）往右数 → O(n)

3. JS 模板

3.1 分组（Map of arrays）

function groupByKey(items, getKey) {
  const map = new Map()
  for (const item of items) {
    const key = getKey(item)
    if (!map.has(key)) map.set(key, [])
    map.get(key).push(item)
  }
  return [...map.values()]
}

3.2 字符计数 key（异位词）

function charCountKey(s) {
  const count = new Array(26).fill(0)
  for (const ch of s) {
    count[ch.charCodeAt(0) - 97]++
  }
  return count.join('#')
}

3.3 连续序列（只从起点扩展）

function longestConsecutive(nums) {
  const set = new Set(nums)
  let ans = 0

  for (const num of set) {
    if (set.has(num - 1)) continue // 不是起点，跳过
    let len = 1
    while (set.has(num + len)) len++
    ans = Math.max(ans, len)
  }

  return ans
}

---

4. 精讲 · 242 有效的字母异位词

题意：判断 s 和 t 是否为异位词（字母相同、次数相同）。

套路：长度不等直接 false；计数数组两边消。

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
  if (s.length !== t.length) return false

  const count = new Array(26).fill(0)

  for (let i = 0; i < s.length; i++) {
    count[s.charCodeAt(i) - 97]++
    count[t.charCodeAt(i) - 97]--
  }

  return count.every((c) => c === 0)
}

也可：用 Map 或排序 s.split('').sort().join('')——面试说清复杂度：排序 O(n log n)，计数 O(n)。

---

5. 精讲 · 49 字母异位词分组

题意：把异位词分到同一组。

套路：每条字符串映射到同一个 key，Map<key, string[]>。

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  const map = new Map()

  const getKey = (s) => {
    const count = new Array(26).fill(0)
    for (const ch of s) {
      count[ch.charCodeAt(0) - 97]++
    }
    return count.join('#')
  }

  for (const s of strs) {
    const key = getKey(s)
    if (!map.has(key)) map.set(key, [])
    map.get(key).push(s)
  }

  return [...map.values()]
}

key 为何用 count.join('#')？
避免 "11" 和 "2" 这种拼接歧义；# 作分隔即可。

另一种 key：[...s].sort().join('')——好写，但单次 O(k log k)，k 为单词长度。

---

6. 精讲 · 128 最长连续序列

题意：未排序数组，求最长连续整数序列长度。要求 O(n)。

套路：

1. 全部放进 Set。
2. 遍历 num：若 num - 1 在 Set 里 → 不是起点，跳过。
3. 从 num 开始 num+1, num+2... 数长度。

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  const set = new Set(nums)
  let ans = 0

  for (const num of set) {
    if (set.has(num - 1)) continue

    let len = 1
    while (set.has(num + len)) {
      len++
    }
    ans = Math.max(ans, len)
  }

  return ans
}

为何 O(n)？
每个数最多被「当起点数一次」+「被 while 扫到一次」→ 总次数线性。

边界：空数组 → 0；有重复值 → Set 自动去重，不影响答案。

---

7. 练习清单

题号	名称	难度	备注
242	有效的字母异位词	Easy	本篇已精讲
49	字母异位词分组	Medium	本篇已精讲
128	最长连续序列	Medium	本篇已精讲
347	前 K 个高频元素	Medium	计数 + 排序 / 堆
36	有效的数独	Medium	行 / 列 / 宫 Set 判重

8. 今日验收

• [ ] 能写出 242 的 26 位计数写法
• [ ] 能解释 49 的 key 设计（计数 or 排序）
• [ ] 能口述 128「只从起点扩展」为何 O(n)
• [ ] LeetCode 提交 242、49、128 至少各 1 次 AC

9. 可选 · 记忆唤醒

异位词：计数数组 or sort 当 key → Map 分组
242：同长 + 26 计数增减为 0
128：Set；num-1 存在则跳过；从 num 往后数 len

下一步

→ 10 · 栈