给定一个未排序的整数数组 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

    解法一：哈希表存放右边界

    1. class Solution {
    2.     //哈希表记录当前数的右边界
    3.     public int longestConsecutive(int[] nums) {
    4.         Map<Integer,Integer> map = new HashMap<>();
    5.         //先存入自身的值
    6.         for (int num : nums) map.put(num,num);
    7.         int res = 0;
    8.         for (int num : nums) {
    9.             if (map.containsKey(num)) {
    10.                 int right = map.get(num);
    11.                 while (map.containsKey(right + 1)) {
    12.                     //这步很重要,当right+1存在时,我们就把right的键值对删除,后面就可以判断right的key值不存在跳出循环,保证每个数只被遍历一次保证On
    13.                     map.remove(right);
    14.                     right = map.get(right+1);
    15.                 }
    16.                 res = Math.max(res,right - num + 1);
    17.                 map.put(num,right);
    18.             }
    19.         }
    20.         return res;
    21.     }
    22. }

    解法二：哈希表存放连续区间长度

    1. class Solution {
    2.     //哈希表记录当前数的连续区间长度
    3.     public int longestConsecutive(int[] nums) {
    4.         Map<Integer,Integer> map = new HashMap<>();
    5.         int res = 0;
    6.         for (int num : nums) {
    7.             //只有当哈希表里面没有的数我们才统计
    8.             if (!map.containsKey(num)) {
    9.                 //左连续区间和右连续区间,因为num未存在哈希表中,所以key=num-1,它的value表示区间只能是[num-value,num-1],同理key=num+1,它的value表示区间只能是[num+1,num+value];
    10.                 int left = map.getOrDefault(num-1,0);
    11.                 int right = map.getOrDefault(num+1,0);
    12.                 int curLen = left + right + 1;
    13.                 res = Math.max(res,curLen);
    14.                 //标记num,可以put任意值,如果[left,num]会put num,成为右边界,[num,right],会put num,成为左边界,否则则会成为中间值[left,right];
    15.                 map.put(num,-1);
    16.                 map.put(num-left,curLen);
    17.                 map.put(num+right,curLen);
    18.             }
    19.         }
    20.         return res;
    21.     }
    22. }

    解法三：并查集

    1. class Solution {
    2.     Map<Integer,Integer> map = new HashMap<>();
    4.     private int find(int x) {
    5.         if (!map.containsKey(x)) return 0x3f3f3f3f;
    6.         //路径压缩
    7.         if (map.get(x) != x) map.put(x,find(map.get(x)));
    8.         x = map.get(x);
    9.         return x;
    10.     }
    12.     private void union(int x, int y) {
    13.         int a = find(x);
    14.         int b = find(y);
    15.         if (a == b) return;
    16.         map.put(a,b);
    17.     }
    19.     public int longestConsecutive(int[] nums) {
    20.         for (int num : nums) map.put(num,num);
    21.         for (int num : nums) {
    22.             if (find(num+1) != 0x3f3f3f3f) 
    23.                 union(num,num+1);
    24.         }
    25.         int res = 0;
    26.         for (int num : nums) 
    27.             res = Math.max(res,find(num) - num + 1);
    28.         return res;
    29.     }
    30. }