给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

 

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

 

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
Related Topics
  • 并查集
  • 数组
  • 哈希表

  • 👍 1154
  • 👎 0

    • 哈希表，一次遍历，时间复杂度为 O(n) ，并不需要再往当前值两边遍历查询【更新图解】的解法

    以题面中的例子为例分析

    nums = [0,3,7,2,5,8,4,6,0,1]

    我们建立一个HashMap，key存储的是某个数字，value存储的是这个数字对应的连续区间的长度

    但是我们真的需要在每插入一个数字的时候，更新整个对应的连续区间里的所有数字的对应连续区间的长度么？

    答案是肯定的 “不”

    如上面的举例数组，我们来尝试分析下

    1. 当第一个数字0的时候，我们在哈希表中插入一个记录key=0，value=1
    2. 当面有第二个数字3的时候，继续在哈希表中插入一个记录，key=3，value=1
    3. 下一个7，相同key=7，value=1
    4. 这时候我们遇到了数字2，在插入哈希表之后，判断下，此时哈希表中有1么？没有，那么跳过。但是又有没有3呢？有的，3对应的长度为1，所以我们知道了哈希表中此时应当更新这些信息：key=2，value=2；key=3，value=2
    5. 后面太多距离太远的，为了减少分析中的情况讨论暂时忽略。
    6. 然后我们来到了数字4，此时我们发现前面有个3，他对应的长度是2，那么我们应该把4对应的长度更新为3，而3前面对应的长度2的开头key=2的位置也应当更新为长度3，就有了key=4,value=3;key=2,value=3
    7. 直接到结尾数字0 的时候，此时哈希表中已经有了0了，可以直接跳过
    8. 最后遇到了数字1，在这里我们先确认下此时哈希表中的值，这里将是最关键的一步
    key=0, value = 1
key=2, value = 3
key=3, value = 2
key=4, value = 3

    1的左边有0，长度为1，同时右边有2，长度为3，所以能够组合得到的长度是

    左边的长度1 + 右边的长度3 + 1数字本身的长度1 = 长度5

    最终这里的哈希表中的值的情况如下

    key=0, value = 5
key=1, value = 1
key=2, value = 3
key=3, value = 2
key=4, value = 5

    在这个结果中，如果又多了一个数字5，需要修改的应该是key=0, value = 6; key=5, value = 6

    到这里其实应当已经非常明了了，下面直接看代码吧

    代码
    class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length==0)return 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        int max = 1;
        for (int num : nums) {
            if (map.containsKey(num)){
                continue;
            }
            map.put(num,1);
            int l = num;
            int r = num;
            int length = 1;

            if (map.containsKey(num-1)){
                l = num - map.get(num-1);
                length += map.get(l);
            }
            if (map.containsKey(num+1)){
                r = num + map.get(num+1);
                length += map.get(num+1);
            }
            map.put(l,length);
            map.put(r,length);
            max = Math.max(max,length);
        }

        return max;
    }
}

    补个画图说明，可能关文字不太好理解？

    横向蓝色的是哈希表的key，竖直方向的橙色为当前遍历到的数字，红色部分为当前遍历的时候插入的值，黄色部分表示当前遍历的时候更新的值

    前面几步太简单，省略了

    直接快进到图上插入数字6的时候讲解，覆盖了完整的判断处理逻辑

    1. 插入数字6，暂时记录哈希表上6对应的值为1
    2. 判断左边一个key 也就是 6-1的情况，读取哈希表key=5的值，知道5对应的最长连续长度为4，那么也就可以知道应该是从数字2到5都有，这样才能得到一个以5结尾的长度4的序列，暂时记下来，我们知道了左边界为2，左边长度为4
    3. 再判断右边，也就是key为7的值，读取哈希表知道了7对应的长度为2，那么也就知道了右边界为8，右边的长度为2
    4. 这样就知道了左边长度是4、右边长度是2，当前数字6还占一个长度1，那么总连续长度为 4 + 2 + 1 = 7
    5. 更新左右两个边界的key对应的长度、把key=2的左边界value更新为7，把key=8右边界的value更新为7