LeetCode.128.Longest Consecutive Sequence 最长连续序列

题目描述

128 Longest Consecutive Sequence
https://leetcode-cn.com/problems/longest-consecutive-sequence/

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

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

示例:

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

---

解题过程

O(n^2)暴力搜索

暴力解法的思想是外层循环遍历数组中每个元素 i，然后内层循环找 i+1 是否在数组中，统计长度并和当前最大连续序列长度对比更新。可以将数组元素放入 set ，就可以实现 O(1) 找 i+1 是否在数组中，但时间复杂度还是 O(n^2)。

O(n)哈希剪枝

以 [100, 4, 200, 1, 3, 2] 为例，外层循环以 1 开始时，得到最长连续序列长度为 4，即 [1,2,3,4]，之后外层循环遍历到 2,3,4 时其实都是无效的遍历，因为以 2,3,4 开头的序列肯定在以 1 开头的序列中，可以想办法把这些重复的操作去掉。
怎么优化呢？
外层循环我们只需要遍历那些不是某个元素的 +1 后续的元素，即跳过处于某个连续序列中间的元素，就可以把 2,3,4 跳过，还是利用 set，我们只从 i-1 不在 set 中的元素开始遍历查找。

注意两点：
1、数组元素有可能是 int 最小值，此时 i-1 会越界，需要特殊判断一下，当然测试用例中没有这种数据，不考虑也能过。
2、进一步的优化，我们只需要遍历 set 中去重后的元素，而不是原始数组 nums，这个优化对于原始数组中有大量重复数据时有不错的效果。

时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV202006 {
    public int longestConsecutive(int[] nums) {
        if (null == nums || nums.length < 1) {
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            set.add(i);
        }
        int maxLength = 0;
        for (int i : nums) {
            // 只遍历没有出现在其他连续序列中的元素， 即 i-1 不存在 set 中的
            if (!set.contains(i - 1)) {
                int length = 1;
                int j = i;
                while (set.contains(j + 1)) {
                    j++;
                    length++;
                }
                maxLength = Math.max(maxLength, length);
            }
        }
        return maxLength;
    }
}

并查集

基本思想是每个连续序列中的元素合并到并查集的一个集合中，代表元是这个集合最小或最大的元素，然后找size最大的集合的size就行。或者也可以找每个元素和他的代表元之间的差值。并查集可以在遍历数组的过程中动态的构造。

---

GitHub代码

algorithms/leetcode/leetcode/_128_LongestConsecutiveSequence.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_128_LongestConsecutiveSequence.java

---