题目：
Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4. Your algorithm should run in O(n) complexity.注意点 1：在一个数组中找到最长的连续序列。 2：数组未排序 3：可能存在重复数字
思路 1：先排序，然后根据排序结果依次遍历搜索连续序列 2：因为存在重复，想到set集合。首先将数组去全部放入set集合中。然后遍历删除左右数字。 3：新建一个map集合，key是当前数字的值，value是已经在map集合中该数字的连续序列长度。依次将数组放入map集合中，在放入过程中，如果是连续序列，只要找到小1和大1的map的值，然后进行相加+1即可。在过程中，除了要更新当前的值，还需要更新左右结点的值。
实现代码
//思路1 class Solution { public int longestConsecutive(int[] nums) { if(nums == null || nums.length == 0) return 0; if(nums.length == 1) return 1; //对数组进行排序再去找最长序列 Arrays.sort(nums); int res = 0, tmp = 1; for(int i = 0; i < nums.length-1; i++){ //可能存在重复 if((nums[i] == nums[i + 1]) || (nums[i] == nums[i + 1] - 1)){ //如果不重复，就加1，重复略过 if(nums[i] == nums[i + 1] - 1) tmp += 1; } else { res = Math.max(res , tmp); tmp = 1; } } //不能直接返回res，遇到[1,2,3,4,5]这种可能之前没有进入else语句 return Math.max(res , tmp); } } //思路2 class Solution { public int longestConsecutive(int[] nums) { if(nums == null || nums.length == 0) return 0; if(nums.length == 1) return 1; //加入set集合，去重 Set<Integer> set = new HashSet<>(); for(int n : nums) set.add(n); int res = 0; for(int n: nums){ int count = 0; //如果set已经空，则返回； if(set.isEmpty()) break; //对于数组中的数，删除左边的数 int val = n; while(set.remove(val--)) count ++; //删除右边的数,(n已在上式中删除) val = n + 1; while(set.remove(val++)) count ++; //判断完每个连续的数块，就更新一次最大值 res = Math.max(count,res); } return res; } } //思路3 class Solution { public int longestConsecutive(int[] nums) { int res = 0; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int n : nums){ if(!map.containsKey(n)){ int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0; int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0; // sum: length of the sequence n is in int sum = left + right + 1; map.put(n, sum); // keep track of the max length res = Math.max(res, sum); // extend the length to the boundary(s) // of the sequence // will do nothing if n has no neighbors map.put(n - left, sum); map.put(n + right, sum); } else { // duplicates continue; } } return res; } }