# 124. Longest Consecutive Sequence

Leave a commentSeptember 3, 2016 by oneOokay

没想出来O(n)的算法，只能想到超级复杂的。看了答案用hashset还挺简单的，大概的了解一下记一下吧

public int longestConsecutive(int[] num) {

// write you code here

HashSet<Integer> set = new HashSet<Integer>();

for (int i = 0; i < num.length; i ++) {

set.add(num[i]); //把所有元素存到hashset中

}

int longest = 0;

for (int i = 0; i < num.length; i ++) {

int down = num[i] – 1; //找num[i]小的consequence

while (set.contains(down)){

set.remove(down); //在hash表中存在的话，remove，再继续找下一个比它小的consequence

down –;

}

int up = num[i] + 1; //同样的找比num[i]大的consequence

while (set.contains(up)){

set.remove(down);

up ++;

}

longest = Math.max(longest, up – down – 1);

}

return longest;

}

Advertisements