每日题解:LeetCode 128. 最长连续序列

题目地址
个人博客地址

题目描述

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

要求算法的时间复杂度为 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);
最近的文章

每日题解:LeetCode 1117. H2O 生成

题目地址个人博客地址题目描述给定一个未排序的整数数组,找出最长连续序列的长度。要求算法的时间复杂度为O(n)。示例:输入:[100,4,200,1,3,2]输出:4解释:最长连续序列是[1,2,3,4]。它的长度为4。解法JAVAclassSolution{publicintlongestConse…

继续阅读
更早的文章

每日题解:LeetCode 面试题29. 顺时针打印矩阵

题目地址个人博客地址题目描述输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。示例1:输入:matrix=[[1,2,3],[4,5,6],[7,8,9]]输出:[1,2,3,6,9,8,7,4,5]示例2:输入:matrix=[[1,2,3,4],[5,6,7,8],[9,10,11,…

继续阅读