经典150题 - 哈希表

383. 赎金信

判断 ransomNote 能否由 magazine 的字符构成（每个字符只能用一次），字符仅限小写字母。

var canConstruct = function(ransomNote, magazine) {
  // 如果赎金信更长，肯定不行
  if (ransomNote.length > magazine.length) return false;
 
  // 桶计数：26 个小写字母
  const count = new Array(26).fill(0);
  // a -> 0, b -> 1, ..., z -> 25
  const aCode = 'a'.charCodeAt(0);
 
  // 统计杂志中每个字符出现次数
  for (const c of magazine) count[c.charCodeAt(0) - aCode]++;
 
  // 遍历赎金信，消耗字符
  for (const c of ransomNote) {
    const idx = c.charCodeAt(0) - aCode;
    if (count[idx] === 0) return false; // 字符不够用
    count[idx]--;
  }
 
  return true;
};

205. 同构字符串

判断两个字符串是否同构：相同位置的字符存在一一映射关系，且不同字符不能映射到同一字符。

var isIsomorphic = function(s, t) {
  if (s.length !== t.length) return false;
 
  const lastS = {}, lastT = {};
  // 记录每个字符上一次出现的位置（i+1 避免 0 与 undefined 混淆）
  for (let i = 0; i < s.length; i++) {
    if (lastS[s[i]] !== lastT[t[i]]) return false;
    lastS[s[i]] = i + 1;
    lastT[t[i]] = i + 1;
  }
  return true;
};

290. 单词规律

var wordPattern = function(pattern, s) {
  const words = s.split(' ');
  if (pattern.length !== words.length) return false;
 
  // 用 Map 避免原型链属性干扰（如 "constructor"）
  const mapP = new Map(), mapW = new Map();
  for (let i = 0; i < pattern.length; i++) {
    // 记录每个字符/单词的首次出现位置
    if (!mapP.has(pattern[i])) mapP.set(pattern[i], i);
    if (!mapW.has(words[i])) mapW.set(words[i], i);
    // 比较首次出现位置是否一致
    if (mapP.get(pattern[i]) !== mapW.get(words[i])) return false;
  }
  return true;
};

242. 有效的字母异位词

判断两个字符串是否由相同字符以相同数量组成（仅含小写字母）。

var isAnagram = function(s, t) {
  if (s.length !== t.length) return false;
 
  // 一个桶：s 加、t 减，最终应全部归零
  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]--;
  }
 
  // 检查是否全零
  for (const c of count) {
    if (c !== 0) return false;
  }
  return true;
};

49. 字母异位词分组

将字符组成相同的字符串归为一组（仅含小写字母）。

var groupAnagrams = function(strs) {
  const map = new Map();
  for (const str of strs) {
    // 统计每个字母出现次数
    const count = new Array(26).fill(0);
    for (let i = 0; i < str.length; i++) {
      count[str.charCodeAt(i) - 97]++;
    }
    // 用字符编码压缩成 26 位 key，比 join(',') 更短更快
    const key = String.fromCharCode(...count);
    if (map.has(key)) {
      map.get(key).push(str);
    } else {
      map.set(key, [str]);
    }
  }
  return Array.from(map.values());
};

1. 两数之和

找到两个数之和等于 target 的下标，每个输入只有唯一解。

var twoSum = function(nums, target) {
  // 存储已遍历的值 -> 下标
  const prev = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    // 前面出现过 complement，配对成功
    const j = prev.get(complement);
    if (j !== undefined) return [j, i];
    prev.set(nums[i], i);
  }
};

202. 快乐数

反复求各位平方和，判断最终能否收敛到 1，而非进入循环。

var isHappy = function(n) {
  const sumSquares = (x) => {
    let sum = 0;
    while (x) {
      const d = x % 10;
      sum += d * d;
      x = Math.floor(x / 10);
    }
    return sum;
  };
 
  const seen = new Set();
  while (n !== 1) {
    if (seen.has(n)) return false; // 进入循环
    seen.add(n);
    n = sumSquares(n);
  }
  return true;
};

219. 存在重复元素 II

判断是否存在距离 ≤ k 的相同元素。

var containsNearbyDuplicate = function(nums, k) {
  const lastIdx = new Map();
  for (let i = 0; i < nums.length; i++) {
    const j = lastIdx.get(nums[i]);
    if (j !== undefined && i - j <= k) return true;
    lastIdx.set(nums[i], i);
  }
  return false;
};

128. 最长连续序列

在 O(n) 时间内找出未排序数组中最长连续序列的长度。

var longestConsecutive = function(nums) {
  if (!nums.length) return 0;
 
  const set = new Set(nums);
  let maxLen = 0;
 
  for (const num of set) {
    // 只从连续序列的最小值开始统计
    if (set.has(num - 1)) continue;
 
    let cur = num;
    while (set.has(cur + 1)) cur++;
    maxLen = Math.max(maxLen, cur - num + 1);
  }
 
  return maxLen;
};

相关笔记

• 集合与字典
• 哈希表专题
• GRD 数组刷题