题目描述

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

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

https://leetcode-cn.com/problems/longest-consecutive-sequence/

解法1

题目要求时间复杂度O(n)，那就说明只能扫描一次，排序什么的是不行的。我们可以举个简单的例子，来启发我们寻找合适的算法解决问题。

例1: nums = {1,2,0,5,4,3,-1}

• 遇到1，那么1独立成一个序列，长度是1；
• 遇到2，1和2能连在一起成为长度为2的序列{1,2}；
• 遇到0，那么0可以和刚刚{1,2}的序列成为长度为3的连续序列{0,1,2}；
• 遇到5，那么5需要独立成一个序列，长度是1；
• 遇到4，那么5和4能够接上，形成长度为2的序列{4,5}；
• 遇到3，那么3会将刚刚发现的两个序列{0,1,2}与{4,5}接上，形成{0,1,2,3,4,5}，长度为6。
• 遇到-1，那么-1将会与刚刚形成的序列{0,1,2,3,4,5}连接，形成长度为7的序列{-1,0,1,2,3,4,5}

根据例1，我们可以使用map来记录数字与数字所对应序列的长度。每当添加一个新的数字num，检查num-1与num+1是否存在；如果存在，那么就将左右两部分与新添加的数字num连接起来，形成新的序列。然后更新新序列两端，为新序列的长度。

为什么只需要更新新序列左右两端的值，而不是新序列每一个数字的值？这是因为，序列相联时，只会取端点的值。根据上面的分析，我们能够编写出下面代码。时间复杂度O(n), 空间复杂度O(n)。

class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;

        for (int num : nums) {
            if (!map.containsKey(num)) {
                Integer leftLen = map.getOrDefault(num - 1, 0);
                Integer rightLen = map.getOrDefault(num + 1, 0);
                int connectedLen = leftLen + 1 + rightLen;

                res = Math.max(res, connectedLen);

                map.put(num, connectedLen);
                map.put(num - leftLen, connectedLen); // 取到新序列左端点
                map.put(num + rightLen, connectedLen); // 取到新序列右端点
            }
        }

        return res;
    }
}