128. Longest Consecutive Sequence
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) { if (nums.length<=1) return nums.length; Map<Integer, Integer> map= new HashMap<>(); int res=0; for (int ele: nums){ if (!map.containsKey(ele)){ int left= map.containsKey(ele-1)?map.get(ele-1):0; int right= map.containsKey(ele+1)?map.get(ele+1):0; int sum= left+right+1; res=Math.max(res,sum); map.put(ele,sum); map.put(ele-left,sum); map.put(ele+right,sum); } } return res; } }
