> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/data-structure/128.longest-consecutive-sequence.md).

# 128.Longest-Consecutive-Sequence

## 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

```java
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

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

    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;
  }
}
```