This problem has a O(n) solution?

Use a set to contain all the number.
And only contain the areas have not appeared consecutive sequence during the online computing.//about the question : the number appears more than once only count once. (Tried) public int longestConsecutive(int[] num) { if(num == null) return 0; Set<Integer> set = new HashSet<Integer>(); int max = 1; for (int n : num) set.add(n); for (int n : num) { int count = 1, i = 0; while (set.contains(n  ++i)) { count ++; set.remove(n  i); } i = 0; while (set.contains(n + ++i)) { count ++; set.remove(n + i); } max = Math.max(count, max); } return max; }

The intuitive idea is to 'chain' the consecutive numbers together. To do this, we can set up a parent and a child pointer, i.e., parent[i] = j means the parent of num[i] is j. To be efficient, you need to use a hash map to map the value to its index in the array.
After you construct the chain, given any number v of index i, you can simply, traverse parent/child to get the length of chain, and mark the elements as visited. Thus, each element will only be visited once.
An improvement is to record the range directly. The code is given in another post.

The hash give you O(1) only if there no repetitions on the result of the hash function.
Given that hash(x) returns the same value for the same value of x by definition, if the element x is repeated twice you don't have O(1).Now if you insert N elements into the hash map that is not O(1), but O(1) or O(logN) depending on the implementation, you end up with something greater than O(N).

 RadixSort takes O(n) time.
 Scan a array to get the longest consecutive sequence takes O(n) time.
so we can combine
public int longestConsecutive(int[] num) { num = this.radixSort(num); int length = 1, clength = 1; for (int i = 1; i < num.length; i++) { if (num[i] == num[i  1]) continue; if (num[i] == num[i  1] + 1) { clength++; } else { if (clength >= length) { length = clength; } clength = 1; } } return clength > length ? clength : length; }
int[] radixSort(int[] num) { int l = Integer.MIN_VALUE; for (int n : num) { if (Math.abs(n) > l) l = Math.abs(n); } int base = 1; while (l / base != 0) { num = this.countSort(num, base); base *= 10; } return num; } private int[] countSort(int[] num, int base) { int[] psn = new int[num.length]; int[] counts = new int[19]; int[] indexes = new int[19]; for (int n : num) { int tail = this.getTail(n, base); counts[tail] = counts[tail] + 1; } indexes[1] = counts[0]; for (int i = 2; i < counts.length; i++) { indexes[i] = indexes[i  1] + counts[i  1]; } for (int i = 0; i < num.length; i++) { int tail = this.getTail(num[i], base); int index = indexes[tail]; psn[index] = num[i]; indexes[tail] = index + 1; } return psn; } int getTail(int n, int base) { return ((n % (base * 10)) / base) + 9; }