首页 > 代码库 > LeetCode:Longest Consecutive Sequence

LeetCode:Longest Consecutive Sequence

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

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

这个方法依赖hashSet,空间复杂度O(N)

Solution:

public class Solution {    public int longestConsecutive(int[] num) {        HashSet<Integer> set = new HashSet<Integer>();        int length = 0;        for(int e : num){            set.add(e);        }        for(int i = 0; i < num.length;i++){            int l = num[i] -1;            int r = num[i] +1;            int c = 1;            while(set.contains(l)){                c++;                set.remove(l);                l--;            }            while(set.contains(r)){                c++;                set.remove(r);                r++;            }            length = Math.max(length,c);        }        return length;    }}