LeetCode128-最长连续序列

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/longest-consecutive-sequence/

中文链接：https://leetcode-cn.com/problems/longest-consecutive-sequence/

题目详述

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

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

示例:

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

题目详解

  • 运用 Map 存储元素所在连续序列的长度。
  • 遍历数组，如果 map 中存在当前元素 num，表示之前计算过，跳过。如果不存在则进行下一步计算。
  • 计算 num - 1 所在连续序列的长度和 num + 1 所在连续序列的长度，进行合并操作，更新结果，更新当前元素与两个端点的所在连续序列的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode_00128 {

    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int num : nums) {
            if (!map.containsKey(num)) {
                int left = map.getOrDefault(num - 1, 0);
                int right = map.getOrDefault(num + 1, 0);
                int cur = left + 1 + right;
                res = Math.max(res, cur);
                map.put(num, cur);
                map.put(num - left, cur);
                map.put(num + right, cur);
            }
        }
        return res;
    }
}
  • 首先把所有元素添加到 HashSet 。
  • 遍历数组，在 HashSet 中删除当前元素，删除前面与它构成连续序列的元素，删除后面与它构成连续序列的元素，并统计这个区间长度来更新最大值。这一步进行的前提是 HashSet 中存在当前元素，如果不存在，代表之前已经统计过，直接跳过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeetCode_00128 {

    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int res = 0;
        for (int num : nums) {
            if (set.remove(num)) {
                int pre = num - 1;
                int next = num + 1;
                while (set.remove(pre)) {
                    --pre;
                }
                while (set.remove(next)) {
                    ++next;
                }
                res = Math.max(res, next - pre - 1);
            }
        }
        return res;
    }
}