# 128. 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;
}
}
``````

Binary Tree Longest Consecutive Sequence

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

https://leetcode.com/problems/longest-consecutive-sequence/discuss/41055/my-really-simple-java-on-solution-accepted