LeetCode 128. Longest Consecutive Sequence

本文主要是介绍LeetCode 128. 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.

分析
如果允许 O(n log n) 的复杂度，那么可以先排序，可是本题要求 O(n)。 由于序列里的元素是无序的，又要求 O(n)，首先要想到用哈希表。
用一个哈希表 unordered_map

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_map<int, bool> used;for (auto i : nums) used[i] = false;int longest = 0;for (auto i : nums) {if (used[i] == true) continue;int length = 1;used[i] = true;for (int j = i + 1; used.find(j) != used.end(); ++j) {used[j] = true;++length;}for (int j = i - 1; used.find(j) != used.end(); --j) {used[j] = true;++length;}longest = (length < longest) ? longest : length;}return longest;}
};

这篇关于LeetCode 128. Longest Consecutive Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---