最长连续序列

给定一个未排序的整数数组nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

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

核心思路：遍历 $nums$ 中的元素 $x$，以 $x$ 为起点，不断查找下一个数 $x+1,x+2,⋯ $是否在 $nums$ 中，并统计序列的长度。

• 把 $nums$ 中的数都放入一个哈希集合中，这样可以 $O(1)$ 判断数字是否在 $nums$ 中。
• 如果 $x−1$ 在哈希集合中，则不以 $x$ 为起点。为什么？因为以 $x−1$ 为起点计算出的序列长度，一定比以 x 为起点计算出的序列长度要长！这样可以避免大量重复计算。

关于第二点的解释：
当我们遍历数组中的每个元素 $x$ 时，我们检查 $x-1$ 是否存在于哈希集合中。如果 $x-1$ 存在，那么以 $x$ 为起点的连续序列的长度一定不会超过以 $x-1$ 为起点的连续序列的长度。这是因为如果 $x-1$ 存在，那么 $x-1$ 之前的元素也一定存在，所以以 $x-1$ 为起点的连续序列会包含以 $x$ 为起点的连续序列。

因此，如果 $x-1$ 存在于哈希集合中，我们就不考虑以 x 为起点的连续序列，这样可以避免重复计算，提高算法的效率。如果 $x-1$ 不存在，那么我们以 $x$ 为起点，不断查找下一个数 $x+1, x+2, ...$ 是否在哈希集合中，并统计序列的长度。这样，我们就可以找到最长的连续序列的长度。

class Solution {
public:
  int longestConsecutive(vector<int>& nums) {
    nordered_set<int> numset;
    for(auto n:nums){
      numset.insert(n);
    }
    //上面的循环可以直接用下一步的初始化
    //unordered_set<int> numset(nums.begin(),nums.end());
    int res=0;
    int len=0;
    for(auto n:nums){
      if(!numset.count(n-1)){
        len=1;
        while(numset.count(++n)) len++;
        res=max(res,len);
      }
    }
    return res;
  }
};

更新日志

2024/12/13 13:22

查看所有更新日志

• 24fac-prepare interview于 2024/12/13