题目地址：

https://www.lintcode.com/problem/longest-consecutive-sequence/description

给定一个数组，求其最长的由连续数字组成的子集的大小（意思是，形如{k,k+1,k+2,...}\{k,k+1,k+2,...\}{k,k+1,k+2,...}的子集。顺序不要紧）。

思路是用哈希表。先将所有数组都存进哈希表里，然后随机从哈希表里取出一个数$x$，依次在哈希表里删去$x,x+1,x+2,...$，然后再依次删去$x-1,x-2,...$，这样就得到了一个连续数字子集，记录其长度；如此这样，直到哈希表被删干净为止。代码如下：

import java.util.HashSet;
import java.util.Set;public class Solution {/*** @param num: A list of integers* @return: An integer*/public int longestConsecutive(int[] num) {// write your code hereSet<Integer> set = new HashSet<>();for (int n : num) {set.add(n);}int res = 0;while (!set.isEmpty()) {// 取出一个数并删去int cur = set.iterator().next();set.remove(cur);// 初始化子集大小len为1int len = 1, i = 1;// 删除cur + 1, cur + 2, ...while (set.contains(cur + i)) {set.remove(cur + i);i++;len++;}i = 1;// 删除cur - 1, cur - 2, ...while (set.contains(cur - i)) {set.remove(cur - i);i++;len++;}// 更新答案res = Math.max(res, len);}return res;}
}

时空复杂度$O(n)$。