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.
Solution: 用hashset。up, down记录可达到的上/下限,同时把数从hashset remove
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
Set<Integer> hashset = new HashSet<>();
int ans = 1;
for (int num : nums) {
hashset.add(num);
}
for (int num : nums) {
int down = num - 1;
while (hashset.contains(down)) {
hashset.remove(down);
down--;
}
int up = num + 1;
while (hashset.contains(up)) {
hashset.remove(up);
up++;
}
ans = Math.max(ans, up - down - 1);
}
return ans;
}