整数流场景下最长连续子序列求解的时间复杂度优化方案问询

当然有办法把时间复杂度降到**O(N)**啦，核心思路是用哈希表（字典）来记录每个数字对应的连续序列长度，具体逻辑是这样的：

• 首先，维护一个哈希表，键是已经加入的数字，值是这个数字所在的最长连续序列的长度。
• 当新加入一个数字num时：
  1. 如果num已经在哈希表里了，直接跳过（避免重复处理）。
  2. 先查num-1在哈希表中的值，这是左边相邻数字所在序列的长度；再查num+1的值，这是右边相邻数字所在序列的长度。
  3. 当前num能形成的新序列长度就是left_length + right_length + 1。
  4. 关键一步：只需要更新这个新序列的左右两个端点的长度值就行——因为中间的数字后续不会再被用到（只有当新数字刚好是端点的邻居时才会触发查询）。比如，新序列的左端点是num - left_length，右端点是num + right_length，把这两个端点对应的哈希表值都更新为新的序列长度。
  5. 实时更新全局的最长序列长度。

举个例子对应你的输入场景：

输入10：哈希表存{10:1}，最长长度1
输入12：哈希表存{10:1,12:1}，最长长度1
输入11：查10的长度是1，12的长度是1，新长度是1+1+1=3。然后更新左端点10和右端点12的值为3，哈希表变成{10:3,11:3,12:3}，最长长度3
输入20：哈希表加{20:1}，最长长度还是3

这种方法每个数字只会被处理一次，不会有重复的遍历操作，所以整体时间复杂度是线性的。

内容的提问来源于stack exchange，提问作者Deepak Sikaria