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.

解题思路：首先构造一个关联容器unordered_map<int, bool> used;用来记录每个元素是否使用。对数组中的每个元素，以该元素为中心，通过+1和-1往右和往左筛查关联容器是否包含改元素的相邻元素，直到不连续为止，记录下最长的长度。

参考代码：

#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;


class Solution
{
 public:
  int longestConsecutive(const 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]) 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 = max(longest, length);
    }
    return longest;
  }
};


int main()
{
    int a[] = {300, 4, 200, 9, 3, 2, 8, 7, 6, 5};
    Solution solu;
    vector<int> vec_arr(a, a + 10);
    int res_vec_len = solu.longestConsecutive(vec_arr);
    cout << "original length: " << vec_arr.size() << endl
         << "processed length: " << res_vec_len << endl;

    return 0;
}

运行结果：

original length: 10
processed length: 8