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.
public class Solution { public int longestConsecutive(int[] nums) { Map<Integer,Integer> map = new HashMap<Integer,Integer>(); int longest = 0; int size = nums.length; for(int i=0;i<size;i++) { if(map.containsKey(nums[i])) continue;//排除重复 map.put(nums[i],1); int start = nums[i]; int end = nums[i]; if(map.containsKey(nums[i]+1)) end = nums[i]+map.get(nums[i]+1); if(map.containsKey(nums[i]-1)) start = nums[i]-map.get(nums[i]-1); longest = Math.max(longest,end-start+1); map.put(start,end-start+1);//更新左边界 map.put(end,end-start+1);//更新右边界 } return longest; } }
Longest Consecutive Sequence *
原文：http://www.cnblogs.com/mrpod2g/p/4470966.html