问题： 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.

方法1

先对数组进行排序，然后遍历数组中的元素查找最长连续序列。

  • 使用变量longest进行记录最后结果
  • 从当前元素开始check是否连续，记录长度，并与最大长度进行比较
  • 如果小于最大长度，跳转到当前位置+记录长度进行下一轮check
  • 如果数组长度小于已记录的最大长度即可退出check

不过，排序的时间复杂度已经会达到LeetCode-128.最长连续序列 - 图1#card=math&code=O%28nlogn%29&height=20&width=67)，所以最终的时间复杂度会超出要求的LeetCode-128.最长连续序列 - 图2#card=math&code=O%28n%29&height=20&width=36)。

*方法2

使用hash表存储所有出现过的元素，对于每一个元素，以该元素为中心向左右两个方向进行扩张，直到不连续为止，记录下最长的长度。

  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_set>
  5. using namespace std;
  7. //时间复杂度O(n)，空间复杂度O(n)
  8. int longestConsecutive(const vector<int> nums) {
  9.     unordered_set<int> my_set;
  10.     for (auto i : nums)
  11.         my_set.insert(i);
  12.     int longest = 0;
  13.     for (auto i : nums) {
  14.         int length = 1;
  15.         for (int j = i - 1; my_set.find(j) != my_set.end(); j--) {
  16.             //针对数组中的一个连续序列，这里一定能完整获取到全部元素
  17.             //所以，这里直接对hash表中的元素进行删除
  18.             my_set.erase(j);
  19.             length++;
  20.         }
  21.         for (int j = i + 1; my_set.find(j) != my_set.end(); j++) {
  22.             my_set.erase(j);
  23.             length++;
  24.         }
  25.         longest = longest >= length ? longest : length;
  26.     }
  27.     return longest;
  28. }
  30. //int main() {
  31. //    vector<int> nums= {100, 4, 200, 1, 3, 2};
  32. //    cout<<longestConsecutive(nums) << endl;
  33. //    return 0;
  34. //}

Points

  • auto：自动变量
  • erase()：删除容器中与传入参数hash值相同的元素