发表于: 更新于: 浏览: 579

题目地址
个人博客地址

题目描述

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

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

示例:

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

解法

JAVA

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

解题思路

这题目虽然是一个困难难度的题目，但是用上了set就比较简单了
假设X是最长连续序列的第一个数，我们只需要判断其 x+1, x+2,⋯ 是否存在，就可以了，判断是否存在使用set就可以了

Set<Integer> set=new HashSet<>();
for (int num : nums) {
set.add(num);
}

怎么确定当前数字就是序列的开始？
我们可以将当前数字-1，如果当前数字-1存在，那就表明当前数字在序列的中间

//左边的数不存在，表示当前数字是序列的开始
 if(!set.contains(num-1)){
 }

然后，寻找X+1，X+2

int temp=0;
for (int tempNum =num; set.contains(tempNum); tempNum++) {
temp++;
}

其实也可以用while,但是我觉得用for循环可以将赋值、比较、累加都能一行代码实现，就使用了for循环
寻找最大的序列

res = Math.max(res, temp);