Longest Consecutive Sequence (M)

题目

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: 4
Explanation: 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 <= 10^5
• -10^9 <= nums[i] <= 10^9

---

题意

给定一个数组，从中选择若干数字组成序列，使该序列中的数字依次递增加一，求满足的最长的序列。

思路

O(N)方法：先将所有数存入HashSet中，利用HashSet找到每一个满足序列的第一个数字(即找到数字num，使得num在set中，但num-1不在set中)，从该数字出发求出整个序列的长度。实际上每个数字被访问了两次，复杂度为O(N)。

---

代码实现

Java

class Solution {
    public int longestConsecutive(int[] nums) {
        int ans = 0;
        Set<Integer> set = new HashSet<>();

        for (int num : nums) {
            set.add(num);
        }

        for (int num : set) {
            if (set.contains(num - 1)) continue;

            int cnt = 1;
            while (set.contains(num + 1)) {
                cnt++;
                num++;
            }

            ans = Math.max(ans, cnt);
        }

        return ans;
    }
}