# 128.Longest-Consecutive-Sequence

## ้ข็ฎๅฐๅ

https://www.lintcode.com/problem/longest-consecutive-sequence

https://leetcode.com/problems/longest-consecutive-sequence/

## ้ข็ฎๆ่ฟฐ

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

Your algorithm should run in O(n) complexity.

Example:
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.``````

## ไปฃ็ 

### Approach #1 One Pass

``````public class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
Arrays.sort(nums);

int longestStreak = 1;
int currentStreak = 1;

for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i - 1]) {
if (nums[i] == nums[i - 1] + 1){
currentStreak += 1;
} else {
longestStreak = Math.max(longestStreak, currentStreak);
currentStreak = 1;
}
}
}
return Math.max(longestStreak, currentStreak);
}
}``````

### Approah 2: HashSet and Intelligent Sequence Building

``````public class Solution {
public int longestCOnsecutive(int[] nums) {
Set<Integer> numSet = new HashSet<Integer>();
for (int num : nums) {
}

int longestStreak = 0;

for (int num : numSet) {
if (!numSet.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (numSet.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}

longestStreak = Math.max(longestStreak, currentStreak);
}
}

return longestSteak;
}
}``````

Last updated