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

例如，

给出 [100, 4, 200, 1, 3, 2]，

这个最长的连续序列是 [1, 2, 3, 4]。返回所求长度： 4。

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

详见：https://leetcode.com/problems/longest-consecutive-sequence/description/

Java实现：

方法一：

class Solution {    public int longestConsecutive(int[] nums) {        int res=0;        Set
     
       s=new HashSet
      
       ();        for(int num:nums){            s.add(num);        }        for(int num:nums){            if(s.remove(num)){                int pre=num-1;                int next=num+1;                while(s.remove(pre)){                    --pre;                }                while(s.remove(next)){                    ++next;                }                res=Math.max(res,next-pre-1);            }        }        return res;    }}
      
     

方法二：

class Solution {    public int longestConsecutive(int[] nums) {        int res = 0;        Map
     
       m = new HashMap
      
       ();        for (int num : nums) {            if (!m.containsKey(num)){                int pre = m.containsKey(num - 1) ? m.get(num - 1) : 0;                int next = m.containsKey(num + 1) ? m.get(num + 1) : 0;                int sum = pre + next + 1;                m.put(num, sum);                res = Math.max(res, sum);                m.put(num - pre, sum);                m.put(num + next, sum);            }        }        return res;    }}
      
     

参考：https://www.cnblogs.com/grandyang/p/4276225.html