分析

题目要求寻找最长的连续序列，不要求原数组连续，也就是求在数组里出现的数

字能排序得到的最长数组。

---

题解

哈希

我们可以先用哈希表统计出现了什么数字，然后通过遍历哈希表，我们主要需要

用到count函数来判断是否存在这个数字。

写法	特点
count(x)	只返回0/1，简洁，仅用来判断存在与否
find(x)	返回迭代器，找到后可读取/修改value

代码

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int maxLen = 0;
        unordered_map<int, bool> hashTable;
        for (int num : nums) {
            hashTable[num] = true;
        }
        for (auto& pair : hashTable) {
            int num = pair.first;
            // x-1不存在，说明x是连续段起点
            if (!hashTable.count(num - 1)) {
                int curNum = num;
                int curLen = 1;
                while (hashTable.count(curNum + 1)) {
                    curNum++;
                    curLen++;
                }
                if (curLen > maxLen) {
                    maxLen = curLen;
                }
            }
        }
        return maxLen;
    }
};

精简版本

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end());
        int maxLen = 0;
        for (int x : st) {
            if (!st.count(x - 1)) {
                int cur = x, len = 1;
                while (st.count(cur + 1)) {
                    cur++;
                    len++;
                }
                maxLen = max(maxLen, len);
            }
        }
        return maxLen;
    }
};

时间复杂度$O(n)$

详细分析

设原始数组长度为n，去重后哈希表元素数量为m，一定会满足m ≤ n。

1.构建unordered_map

for (int num : nums) { 
	hashTable[num] = true; 
}

遍历全部$n$个数字，unordered_map插入操作平均$O(1)$。

开销：$O(n)$

2.外层循环遍历哈希表所有键值对

for (auto& pair : hashTable)

一共循环$m$次。

3.核心判断if (!hashTable.count(num - 1))

只有一段连续序列的最小值（序列起点）才会进入内部while；若存在

num - 1，说明当前数字处于连续序列中间，直接跳过内层循环。

4.内层while循环

while (hashTable.count(curNum + 1)) {
	curNum++; curLen++; 
}

对于任意一段连续序列 ([x,x+1,x+2…x+k])：

仅起点 x 会触发 while，把整条连续数字遍历一遍；

序列里其余数字在外层循环都会被 if 拦截，再也不会进入 while。

全局结论：哈希表里所有 m 个元素，在所有 while 中只会被访问总共 m 次。

• 所有while循环整体总共只会遍历m次元素：哈希表里全部 m 个数字，分散在若干段连续区间中，所有 while 加起来，访问元素总次数严格等于m。

外层循环 m 次 + 所有 while 合计遍历 m 次，整体循环开销：$(O(m)$ ≤ $O(n))$。

关于 count ()

unordered_map::count() 查询键是否存在，平均时间 $(O(1))$，不会拉高复杂度量级。

汇总

$O(n) + O(n) = \boldsymbol{O(n)}$

128. 最长连续序列 - 力扣（LeetCode）