## 题目地址

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

## 思路

C++ 解法一：

``````class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int res = 0;
unordered_set<int> s(nums.begin(), nums.end());
for (int val : nums) {
if (!s.count(val)) continue;
s.erase(val);
int pre = val - 1, next = val + 1;
while (s.count(pre)) s.erase(pre--);
while (s.count(next)) s.erase(next++);
res = max(res, next - pre - 1);
}
return res;
}
};
``````

Java 解法一：

``````public class Solution {
public int longestConsecutive(int[] nums) {
int res = 0;
Set<Integer> s = new HashSet<Integer>();
for (int num : nums) s.add(num);
for (int num : nums) {
if (s.remove(num)) {
int pre = num - 1, next = num + 1;
while (s.remove(pre)) --pre;
while (s.remove(next)) ++next;
res = Math.max(res, next - pre - 1);
}
}
return res;
}
}
``````

C++ 解法二：

``````class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int res = 0;
unordered_map<int, int> m;
for (int num : nums) {
if (m.count(num)) continue;
int left = m.count(num - 1) ? m[num - 1] : 0;
int right = m.count(num + 1) ? m[num + 1] : 0;
int sum = left + right + 1;
m[num] = sum;
res = max(res, sum);
m[num - left] = sum;
m[num + right] = sum;
}
return res;
}
};
``````

Java 解法二：

``````public class Solution {
public int longestConsecutive(int[] nums) {
int res = 0;
Map<Integer, Integer> m = new HashMap<Integer, Integer>();
for (int num : nums) {
if (m.containsKey(num)) continue;
int left = m.containsKey(num - 1) ? m.get(num - 1) : 0;
int right = m.containsKey(num + 1) ? m.get(num + 1) : 0;
int sum = left + right + 1;
m.put(num, sum);
res = Math.max(res, sum);
m.put(num - left, sum);
m.put(num + right, sum);
}
return res;
}
}
``````

### 思路2

``````if (nums.length === 0) return 0;
let count = 1;
let maxCount = 1;
// 这里其实可以不需要排序，这么做只不过是为了方便理解
nums = [...new Set(nums)].sort((a, b) => a - b);
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i + 1] - nums[i] === 1) {
count++;
} else {
if (count > maxCount) {
maxCount = count;
}
count = 1;
}
}
return Math.max(count, maxCount);
``````

• 空间换时间

## 代码

``````/*
* @lc app=leetcode id=128 lang=javascript
*
* [128] Longest Consecutive Sequence
*
* https://leetcode.com/problems/longest-consecutive-sequence/description/
*
* algorithms
* Hard (40.98%)
* Total Accepted:    200.3K
* Total Submissions: 484.5K
* Testcase Example:  '[100,4,200,1,3,2]'
*
* 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.
*
*
*/
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
nums = new Set(nums);
let max = 0;
let y = 0;
nums.forEach(x => {
// 说明x是连续序列的开头元素
if (!nums.has(x - 1)) {
y = x + 1;
while (nums.has(y)) {
y = y + 1;
}
max = Math.max(max, y - x); // y - x 就是从x开始到最后有多少连续的数字
}
});
return max;
};
``````

### 思路3

#### 方法一：哈希表

##### 思路和算法

https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/zui-chang-lian-xu-xu-lie-by-leetcode-solution/

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

int longestStreak = 0;

for (int num : num_set) {
if (!num_set.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;

while (num_set.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}

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

return longestStreak;
}
}
``````

评论
0 评论