leetcode：128. 最长连续序列

题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例：

  1. 输入：nums = [100,4,200,1,3,2]
  2. 输出：4
  3. 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
  1. 输入：nums = [0,3,7,2,5,8,4,6,0,1]
  2. 输出：9

解答 & 代码

哈希表

  1. class Solution {
  2. public:
  3.     int longestConsecutive(vector<int>& nums) {
  4.         // 哈希表，存储数组中的数
  5.         unordered_set<int> hashMap;
  6.         for(int i = 0; i < nums.size(); ++i)
  7.             hashMap.insert(nums[i]);
  9.         int result = 0;        // 最长连续序列长度
  10.         // 遍历数组中的每个元素
  11.         for(int i = 0; i < nums.size(); ++i)
  12.         {
  13.             // 仅当当前元素nums[i]是数组中某个连续序列的第一个数，即哈希表中不存在nums[i]-1：
  14.             // 在哈希表中查找以nums[i]为第一个数的连续序列的最大长度
  15.             if(hashMap.find(nums[i] - 1) == hashMap.end())
  16.             {
  17.                 int len = 1;
  18.                 for(int j = nums[i] + 1; hashMap.find(j) != hashMap.end(); ++j)
  19.                     ++len;
  20.                 result = max(result, len);
  21.             }
  22.         }
  23.         return result;
  24.     }
  25. };

复杂度分析：设整数数组 nums 长为 n

  • 时间复杂度 O(n)：外循环遍历 nums 的每个数，时间复杂度 O(n)。而只有当一个数是某个连续序列的第一个数的情况下，才会进入内循环，计算该连续序列的长度，因此数组中的每个数只会进入内循环一次。因此总时间复杂度还是 O(n)
  • 空间复杂度 O(n)：哈希表的空间复杂度

执行结果：

  1. 执行结果：通过
  3. 执行用时：352 ms, 在所有 C++ 提交中击败了 26.93% 的用户
  4. 内存消耗：30.1 MB, 在所有 C++ 提交中击败了 62.43% 的用户