128. 最长连续序列

最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n)的算法解决此问题。

样例

---

Example

示例 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

示例 3：
**输入：**nums = [1,0,1,2]
**输出：**3

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

思路

---

• 方法一：先考虑朴素解法，遍历每一个数，再依次在数组里找有没有下一个数，直到遍历完整个数组。但是这样时间复杂度肯定爆炸了。要想快速知道下一个数有没有，可以先预处理把全部数都存在一个Set里，这样就能快速的找到后面的数了。假如输入是一个以1递增的数组，每个数都要一直数到最后，显然还是O(N
• 方法二：先看示例[100,4,200,1,3,2]，逐个遍历：[[100]]，[[4]、[100]]，[[4]、[100, 200]]，[[1]、[4]、[100, 200]]，[[1]、[3， 4]、[100, 200]]，[[1, 2, 3， 4]、[100, 200]]。最后得到4。可以发现我们是在不断地序列连起来，从而得到最长序列。因此我们需要知道一个数前和后的最长序列长度，然后计算head + 1 + tail就是序列长度了，又因为最大长度更新只会发生在头尾相连时，因此只需要更新序列头尾的长度就能得到结果。需要注意要进行去重，序列中间的长度不会被更新，再次计算可能会导致错误的结果。

答案

---

Java

// 方法一
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int ans = 0;
        for (int num : nums) {
            set.add(num);
        }
        for (int num : set) {
            if (set.contains(num - 1)) {
                continue;
            }
            int cnt = 1;
            while (true) {
                if(!set.contains(num + cnt)){
                    break;
                }
                cnt++;
            }
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
}
 
// 方法二
class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int ans = 0;
        for (int num : nums) {
            if (map.containsKey(num)) {
                continue;
            }
            int head = map.getOrDefault(num - 1, 0);
            int tail = map.getOrDefault(num + 1, 0);
            int length = head + 1 + tail;
            ans = Math.max(ans, length);
            map.putIfAbsent(num, 1);
            map.put(num - head, length);
            map.put(num + tail, length);
        }
        return ans;
    }
}