LeetCode128.最长连续序列

题目

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

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

示例

输入：nums = [100,4,200,1,3,2]

输出：4

解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

输入：nums = [0,3,7,2,5,8,4,6,0,1]

输出：9

思路

由于题目要求的时间复杂度为O(n)，我们看到题目第一时间想到的可能是使用快排然后去寻找数字连续的最长序列，但是使用快排的时间复杂度为O(n*logn)，使用快排肯定会超时，所以我们可以使用哈希表。

时间复杂度为 O(n) 的哈希表思路：

1. 创建一个哈希表，用于存储数组中的数字及其对应的连续序列长度。
2. 遍历数组，对于每个数字 num，执行以下操作：
   • 检查哈希表中是否存在 num，如果存在则跳过当前数字。
   • 获取 num 左侧连续序列的长度 left（从 num-1 开始向左遍历，递减检查哈希表中的数字并累加长度），获取 num 右侧连续序列的长度 right（从 num+1 开始向右遍历，递增检查哈希表中的数字并累加长度）。
   • 计算当前连续序列的长度 length = left + right + 1（加上当前数字 num）。
   • 更新哈希表中 num、num-left 和 num+right 的值为 length，以及更新 maxLength 的值为最长的连续序列长度。
   • 返回 maxLength。

通过使用哈希表，我们可以快速查找数字是否存在，并且在 O(1) 的时间复杂度内获取连续序列的长度。因此，整体算法的时间复杂度为 O(n)。

Code

class Solution {
public:
    int longestConsecutive(vector& nums) {
        unordered_map map;
        int maxLength = 0;
        for (int num : nums) {
            if (map.find(num) == map.end()) {
                int left = map.find(num - 1) != map.end() ? map[num - 1] : 0;
                int right = map.find(num + 1) != map.end() ? map[num + 1] : 0;
                int length = left + right + 1;
                map[num] = length;
                // 更新连续序列两端的长度
                map[num - left] = length;
                map[num + right] = length;
                maxLength = max(maxLength, length);
            }
        }
        return maxLength;
    }
};