题目描述

给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例

输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4
输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9

题目解析

  1. 维护一个hash表,存储题目给出的元素
  2. 访问hash表,如果x - 1元素不存在就说明x元素是连续序列的起始元素
  3. 从x开始向后查询hash表中最大连续的数是多少(假设为y)
  4. 该连续序列的长度就为y - x + 1

Coding

class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int i:nums){
set.add(i);
}
int res = 0;
for(int x:set){
if(!set.contains(x - 1)){
int y = x;
while(set.contains(y + 1)){
y++;
}
res = Math.max(res,y - x + 1);
}
}
return res;
}
}