StarWalker

Where my heart will take me

0%

Leetcode128-longestConsecutiveSequence

Posted on Edited on In Views: Valine:
Solution Report of LeetCode Acceptted

Description

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

Your algorithm should run in O(n) complexity.

Example

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int longestConsecutive(int[] nums) {
        int res = 0;
        HashSet<Integer> set = new HashSet<>();
        for (int num: nums)
            set.add(num);
        for (int num: set){
            if (!set.contains(num-1)){
                int temp = num + 1;
                while(set.contains(temp))
                    temp++;
                res = Math.max(res, temp - num);
            }
        }
        return res;
    }
}