LeetCode128(最长连续序列)

题目：

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为O(n)。

示例:

输入:[100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

解题思路

将 nums 数组中的每一个数字，作为序列第一个数字，枚举后面的数字，直到有数字在原数组中没出现过。当枚举到数组中没有的数字时（即 currentNum 是一个数组中没出现过的数字），记录下序列的长度，如果比当前最优解大的话就更新。

代码实现

class TwelfthSolution {
public int longestConsecutive(int[] nums) {
Set<Integer> numSet = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
numSet.add(nums[i]);
}
int longSize = 0;

for (int i : numSet) {
if (!numSet.contains(i - 1)) {
int currentNum = i;
int currentSize = 1;
while (numSet.contains(currentNum + 1)) {
currentNum++;
currentSize++;
}

longSize = Math.max(longSize, currentSize);
}
}
return longSize;
}
}