Leetcode-hot100

最长连续序列

By crabboss 2024 年 6 月 29 日

最长连续序列

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

注意该题与最长连续递增序列和最长递增子序列的区别：

1 最长连续递增序列是求索引连续且值递增的子序列长度。
2 最长递增子序列求值递增的子序列长度。
3 最长连续序列是求值连续的子序列长度。

解题思路：

1 先将数据存入集合
2 查看元素i，集合中是否存在i-1，存在则跳过，说明元素i不为序列开头元素
3 不存在则说明是开头元素，继续查看集合是否存在i+1, i+2…元素

代码细节：

class Solution {
public:
    int longestConsecutive(vector& nums) {
        if (nums.size()==1 || nums.size()==0) return nums.size();
        // 1 先将数据存入集合
        int maxValue = 1;
        unordered_set my_set;
        for(auto num:nums) my_set.insert(num);
        // 2 查看元素i，字典中是否存在i-1，存在则跳过，说明元素i不为序列开头元素
        // 3 不存在则说明是开头元素，继续查看字典是否存在i+1, i+2...元素
        for(auto num:my_set){
            if (my_set.count(num-1)) continue;
            else{
                int currentNum = num;
                int length = 1;
                while(my_set.count(currentNum+1)){
                    currentNum++;
                    length++;
                    maxValue = max(maxValue, length);
                }
            }
        }
        return maxValue;
    }
};