LC 128 Longest Consecutive Sequence
30 Dec 2015###Task1 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. return 10.
###java
public class Solution {
/**
* @param nums: A list of integers
* @return an integer
*/
public int longestConsecutive(int[] num) {
// write you code here
if (num == null || num.length == 0) {
return 0;
}
HashMap<Integer, Integer> map = new HashMap<>();
for (int i: num) {
map.put(i, 0);
}
int max = 0;
for (int i: num) {
if (map.get(i) == 1) {
continue;
}
int cur = i;
int len = 1;
while (map.containsKey(--cur)) {
len++;
map.put(cur, 1);
}
cur = i;
while (map.containsKey(++cur)) {
len++;
map.put(cur, 1);
}
max = Math.max(max, len);
}
return max;
}
}
###Points
- No magical part, need to check one by one. But we have to eliminate duplicated checkings by the use of HashMap: 0 value stands for “have this value and available”, 1 value stands for “have this value but not available”