My Blog | 详情

原题：

Description:

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]Output: 4Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]Output: 9

Constraints:

0 <= nums.length <= 105
-109 <= nums[i] <= 109

思路：

\1. 首先想到的是排序，然后判断相邻两数是否差值为 1，计算满足此条件的最长子序列长度。

但复杂度是 T:O(nlogn), 空间复杂度 S:O(1)

题目既然要求使用 O(n) 复杂度来解决问题，那么第一反应是通过外部数据结构来加快搜索，以空间换时间。

\2. 对于一个数 k，在判断它是否属于一个连续子序列时，如果采用原始搜索，只能遍历 n 去查找 k + 1 或 k - 1 是否存在于原数组。

如果我们先将原数组存在 set 里，再判断 k + 1 和 k - 1 是否存在，这样复杂度不是降到 O(1) 了？

然后为了避免每一个数都要双向查找（这样复杂度会接近 O(n^2）)，我们需要选择一边进行跳过，即如果 k - 1 已存在于 set 中，那么直接跳过（因为当 k = k - 1 时也会搜索一次，这次不搜索也没事）。

完整代码：

// AC: Runtime: 275 ms, faster than 20.28% of Java online submissions for Longest Consecutive Sequence.
// Memory Usage: 54.4 MB, less than 42.86% of Java online submissions for Longest Consecutive Sequence.
// .
// T:O(n), S:O(n)
// 
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int max = 1;
        HashSet<Integer> record = new HashSet<>();
        for (int i: nums) {
            record.add(i);
        }

        for (int i: nums) {
            if (!record.contains(i - 1)) {
                int j = i + 1;
                while (record.contains(j)) {
                    j++;
                    max = Math.max(max, j - i);
                }
            }
        }

        return max;
    }
}