LeetCode hot100——最长连续序列
接下来完成 LeetCode hot100 哈希部分的第三题。
最长连续序列
128. 最长连续序列 - 力扣（LeetCode）
想象一下，有一群人站在广场上，每个人胸前都有一个数字编号。你的任务是找到最长的一串连续数字（比如 101, 102, 103, 104）。
但是这题有个极其苛刻的要求：时间复杂度必须为。
这意味着：
不能排序：因为排序最快也要
。
不能嵌套循环直接找：如果你对每个数都去暴力往后数，很可能退化成
。
策略：只从“队长”开始数
如果你是队长，意味着你前面没有兄弟了。
怎么判断你是不是 101 这支队伍的队长？
很简单：看广场上有没有人编号是100。如果没有 100，你就是队长！
如果你是队长，你才开始点名：“102 在吗？103 在吗？104 在吗？...”如果你不是队长（比如你是 102），你就直接闭嘴：因为 101 那个队长自然会去点你的名，你不需要自己跳出来数。
为了实现，我们需要一种能瞬间（
）判断某个人在不在场的能力。没错，就是
Set（集合）！
第一步：全部入库
把数组里所有的数字都扔进一个Set。这一步是为了去重，并且让我们能在时间内查到某个数字是否存在。
第二步：遍历与判断
遍历Set里的每一个数字num：
寻找“队长”：检查
Set里是否有num - 1。如果有，说明当前数字只是某个序列的中段，跳过它（别急，它的队长会来找它的）。
如果没有，恭喜！
num就是一个序列的起始数字（队长）。
队长点名：
从这个
num开始，不停地在Set里找num + 1,num + 2...直到找不到了为止，记录下这支队伍的总长度。
更新记录：拿当前队伍长度去更新全局的“最长长度”。
深度思考：为什么它是？
你可能会问：“点名的时候不是也有循环吗？嵌套循环难道不是吗？”
这就是此算法最精妙的地方：
每一个数字，只有在它是“队长”时，才会触发点名循环。
如果它不是队长，它只会被
if判断一次就跳过了。实际上，每个数字最多只会被进入点名循环一次。
就好比广场上 100 个人，每个人只会被点名一次，虽然有嵌套感，但总工作量依然是，也就是
。
最终代码如下：
function longestConsecutive(nums: number[]): number { const set = new Set<number>(nums); let maxLen = 0; for(const num of set){ if(!set.has(num-1)){ let currentLen=1; let currentNum = num; while(set.has(currentNum+1)){ currentLen++; currentNum++; } maxLen=Math.max(maxLen,currentLen); } } return maxLen; };
接下来再来看看 ACM 机制下要如何书写。
ACM
引入 Node.js 的文件系统模块，用于读取输入：
const fs = require("fs");主函数和调用：
function main(){ try{ const input = fs.readFileSync(0,'utf-8').trim() if(!input) return const str = input.replace(/^nums\s*=\s*/,'') const jsonStr=JSON.parse(str) const result = longestConsecutive(jsonStr) console.log(result) }catch(err){ console.error(err) } } main()input.txt：
nums = [0,3,7,2,5,8,4,6,0,1]然后运行：
node solution.js < input.txt