哈希集合

如何求最长连续序列的长度？

• 去重: 先把数组放进集合;
• 起点判定: 若 num - 1 不在集合中, 则 num 是某段连续序列的起点;
• 计数: 从起点开始不断检查 num + 1 是否在集合中, 累加当前段长度;
• 取最大值: res 维护所有段中最长的长度;
• 复杂度: 时间 O(n), 空间 O(n); 每个数最多被访问两次;

function longestConsecutive(nums: number[]): number {
  const hash = new Set(nums);
  let result = 0;

  for (const num of hash) {
    if (hash.has(num - 1)) continue; // 不是序列起点, 跳过

    let current = num;
    let length = 1;
    while (hash.has(current + 1)) {
      current++;
      length++;
    }
    result = Math.max(result, length);
  }

  return result;
}

如何判断一组数字能否组成顺子？

• 场景: 5 个数字, 0 可以当作任意值;
• 规则一: 忽略 0 后不能有重复值;
• 规则二: 忽略 0 后的最大值与最小值之差不能大于 4;
• 满足两条即可组成顺子;

function checkDynasty(places: number[]): boolean {
  const hash = new Set<number>();
  let min = 14;
  let max = -1;

  for (const place of places) {
    if (place === 0) continue;
    if (hash.has(place)) return false;
    hash.add(place);
    min = Math.min(min, place);
    max = Math.max(max, place);
  }

  return max - min <= 4;
}