Does this problem have an O(N) solution without hash set or hash map? For, I think using hash set or hash map has wired aim of this problem. Why not using mapreduce? It is complexity is length of max sequence.
I come up with a solution, its complexity is approximate O(n) (I have not proved.) based on following naive idea: If we can partition a big problem with equal two small problem, drop first and process the second. we get a O(n) solution, for (n + n/2 + n/(22) + n/(23) + ... ) ~ 2n.
So, my solution is:

input is
{100, 1, 2, 101, 102, 3, 103, 2}

its min value is
1
, we usepivort = 1 + len(seq) = 1 + 8 = 9
to partition the sequence.
we get{1, 2, 2, 3, 100, 101, 102, 103}

the first part is easy to process if we use a vector
{1, 2, 3, nan, nan, nan, nan, nan}
to sample the sequence when partition. 
the second part is just small problem of origin.

Take care, when we partition a long sequence in two half.
I just partition again usingpivort = 1 + (len(seq) + 1) / 2
.
So, My Code is following, considering strange test cases. It is not elegant and I cannot prove is O(N). It is just maybe, but very fast.int longestConsecutive(vector<int> &num) {
if (num.size() <= 1) return num.size();vector<int> temp(num.size());
int curMax = 0;
int starts = 0, ends = num.size();//fast cut off
while (starts < ends && curMax < ends  starts)
{
int curMin = *(min_element(num.begin() + starts,
num.begin() + ends));
int pivort = curMin + (ends  starts);//fill sample vector with invalid data  pivort. for (int t = 0; t < ends  starts; t++) temp[t] = pivort; int i = starts, j = ends; while (i < j) { if (num[i] < pivort) { temp[num[i]  curMin] = num[i]; i++; continue; } if (num[j  1] >= pivort) { j; continue; } swap(num[i], num[j  1]); temp[num[i]  curMin] = num[i]; i++; //no j; to keep invality. } //here must i == j and [starts, i) has been sampled. //now we find curMax; int k = 0; int curPos = 0; do { while (k < ends  starts && temp[k] == pivort) k++; curPos = k; while (k < ends  starts && temp[k] != pivort) k++; if (curMax < k  curPos) curMax = k  curPos; } while (k < ends  starts); //here we should repartition, for our pivort //maybe cut off a sequence. if (temp[ends  starts  1] != pivort) { //now we should repartition. i = starts; j = ends; pivort = curMin + (ends  starts + 1) / 2; while (i < j) { if (num[i] < pivort) { i++; continue; } if (num[j  1] >= pivort) { j; continue; } swap(num[i], num[j  1]); i++; //no j; to keep invality. } } starts = i;
}
return curMax;
}
Some test cases are following:
vector<int> vec = {100, 1, 101, 102, 2};
EXPECT_EQ(longestConsecutive(vec), 3);
vec = {100, 1, 101, 2, 102, 3};
EXPECT_EQ(longestConsecutive(vec), 3);
vec = {100, 1, 101, 2, 102, 3, 999, 4, 1000, 100, 1001, 101, 1003, 101, 1004, 3, 1002};
EXPECT_EQ(longestConsecutive(vec), 6);
vec = {5,8,1,7,4,1,3,7,5,6,3,9,6,6,7,4};
EXPECT_EQ(longestConsecutive(vec), 5);