问题描述
LeetCode 128. 最长连续序列 (opens in a new tab)，难度中等。
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1
输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2
输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109
题解
排序
解题思路：先对数组进行排序，然后遍历数组，判断 nums[index] - nums[index - 1] == 1，如果满足条件，则局部最长连续序列 +1，更新全局最长连续序列，反之局部最长连续序列初始化为 1。注意：存在连续相同的数，例如：[1, 2, 3, 3, 4]。该方法的时间复杂度是 O(nlogn)。
Solution.java
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
// 排序
Arrays.sort(nums);
int max = 1;
// 初始化结果集
int[] result = new int[nums.length];
Arrays.fill(result, 1);
for (int i = 1; i < nums.length; ++i) {
if (nums[i] - nums[i - 1] == 1) {
// 递增，则 result[i] + 1
result[i] = result[i - 1] + 1;
max = Math.max(max, result[i]);
} else if (nums[i] == nums[i - 1]) {
// 相等
result[i] = result[i - 1];
}
}
return max;
}
}哈希
解题思路：将数据存储到 HashSet 中，这样我们可以在常数时间内检查一个元素是否存在；遍历每一个元素，对于每个元素 num，如果 num - 1 不在集合中，说明 num 是一个连续序列的起点；以 num 为起点，检查 num + 1、num + 2、... 是否存在于集合中，直到序列中断。记录下最长的序列长度。时间复杂度为 O(n)。
Solution.java
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
int result = 0;
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
for (int num : set) {
// 只有当 num - 1 不在集合中时，才从 num 开始查找序列。这样可以确保每个序列只被计算一次
if (!set.contains(num - 1)) {
int currNum = num;
int currLen = 1;
while (set.contains(++currNum)) {
currLen++;
}
result = Math.max(currLen, result);
}
}
return result;
}
}