哈希表与 Map / Set 实战

// 运行环境：Node.js 14+
// 保存为 dsa-l8.js，执行：node dsa-l8.js

// 两数之和：暴力 O(n²) vs 哈希 O(n)
function twoSum(nums, target) {
  const seen = new Map()
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]
    if (seen.has(need)) return [seen.get(need), i]
    seen.set(nums[i], i)
  }
  return []
}

// 第一个不重复字符
function firstUniqChar(s) {
  const cnt = new Map()
  for (const ch of s) cnt.set(ch, (cnt.get(ch) || 0) + 1)
  for (let i = 0; i < s.length; i++) if (cnt.get(s[i]) === 1) return i
  return -1
}

// 字母异位词分组
function groupAnagrams(words) {
  const m = new Map()
  for (const w of words) {
    const key = w.split('').sort().join('') // 排序后作指纹
    if (!m.has(key)) m.set(key, [])
    m.get(key).push(w)
  }
  return [...m.values()]
}

console.log(twoSum([2, 7, 11, 15], 9))      // [0, 1]
console.log(firstUniqChar('leetcode'))      // 0
console.log(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat'])) // [[eat,tea,ate],[tan,nat]]