题目
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.
答案
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length == 0) return 0;
int max = 1;
HashSet<Integer> set = new HashSet<Integer>();
for(int num : nums) set.add(num);
for(int sample : nums) {
if(!set.contains(sample)) continue;
int left = sample , right = sample;
while(set.contains(--left)) set.remove(left);
while(set.contains(++right)) set.remove(right);
max = Math.max((right - 1) - (left + 1) + 1, max);
}
return max;
}
}
