128. Longest Consecutive Sequence

核心思路：将nums转为hash set，然后遍历nums查找起点x，如果有x-1在hash set中则x不为起点跳过。如果x为起点则查找x+1, x+2... 在不在hash set中

/**
 * @param {number[]} nums
 * @return {number}
 */
// 核心思路：将nums转为hash set，然后遍历nums查找起点x，如果有x-1在hash set中则x不为起点跳过。
// 如果x为起点则查找x+1, x+2... 在不在hash set中
var longestConsecutive = function (nums) {
  const st = new Set(nums)
  let ans = 0
  for (const x of nums) {
    // x 不为起点
    if (st.has(x - 1)) {
      continue
    }
    // x 为起点
    y = x + 1
    //不断查找下一个数是否在哈希集合中
    while (st.has(y)) {
      y++
    }
    // 循环结束后，y-1 是最后一个在哈希集合中的数
    ans = Math.max(ans, y - x)
    // 小优化：ans 不可能变得更大，不优化会超时
    if (ans * 2 >= st.size) {
      break
    }
  }
  return ans
}