最长连续序列

发表于 分类于 ， ， 阅读次数：

题目描述

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

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

示例 1：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-consecutive-sequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.Map;
import java.util.TreeMap;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set=new TreeSet<>();
        int max=0,j=1;
        int record=0;
        boolean flag=true;
        for(int i:nums)
        {
            set.add(i);
        }
        for(int i:set)
        {
            if(flag)
            {
              record=i;
              flag=false;
              max=1;
              continue;
            }
            if(record+1==i)
            {
                j++;
            }
            else
            {
                j=1;
            }
            if(j>max)
            {
                max=j;
            }
            record=i;
        }

        return max;

    }
}

我的解题思路是利用treeset的排序性质和不可重复性质将数组重新组合，然后再根据题目要求找最大连续数字，该思路找最大连续数字时记得要处理好第一个数，第一个数不用跟前一个数比较是否连续，故直接continue，但是要记得将max赋值为1,否则数组只有一个数的情况不能通过，记得每次record都要记录i的值。

运行结果

执行耗时:52 ms,击败了34.69% 的Java用户

内存消耗:54.4 MB,击败了87.28% 的Java用户

大神题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/longest-consecutive-sequence/solution/zui-chang-lian-xu-xu-lie-by-leetcode-solution/
来源：力扣（LeetCode）

此题解和我的思路差不多，区别是只是用了HashSet来去重，通过!num_set.contains(num - 1)来找每个连续数字串的初始位置，找到以后计算连续数字串的大小，并找出其中最长的数字串的长度。