牛客208701题：深入理解最长连续序列问题
一、问题理解
给定一个无序数组，我们需要找出其中最长的连续数字序列的长度。这里的"连续"指的是数值上的连续，而不是位置上的连续。例如，在数组[100, 4, 200, 1, 3, 2]中，最长的连续序列是[1, 2, 3, 4]，长度为4。
二、暴力解法分析
最直观的解法是对数组排序，然后遍历查找最长连续序列。虽然这种方法简单，但排序的时间复杂度为O(nlogn)，对于大数据量(如n=10^5)来说效率不够高。
三、优化思路
1.将所有数字存入哈希集合
2.对于每个数字，检查它是否是某个连续序列的起点
3.如果是起点，向后查找连续的数字，计算序列长度
4.记录遇到的最大长度
这种方法的时间复杂度为O(n)，因为每个数字最多被访问两次(一次在哈希集合中，一次在序列查找中)。
四、关键点解释
1.为什么只检查序列起点：这样可以避免重复计算。如果一个数字不是序列起点(即存在num-1)，那么它肯定已经被包含在某个更长的序列中了。
2.哈希集合的优势：提供了O(1)的查找时间，使得我们可以快速判断某个数字是否存在。
3.复杂度保证：虽然有两层循环，但内层循环只有在找到序列起点时才会执行，且每个数字最多被访问两次。
五、代码实现
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* max increasing subsequence
* @param arr int整型vector the array
* @return int整型
*/
int MLS(vector<int>& arr) {
if (arr.empty()) return 0;
// 使用哈希集合存储所有数字，实现O(1)查找
unordered_set<int> num_set(arr.begin(), arr.end());
int max_length = 1;
for (int num : num_set) {
// 只有当num是序列的起点时才进入循环
if (num_set.find(num - 1) == num_set.end()) {
int current_num = num;
int current_length = 1;
// 向后查找连续的数字
while (num_set.find(current_num + 1) != num_set.end()) {
current_num++;
current_length++;
}
// 更新最大长度
max_length = max(max_length, current_length);
}
}
return max_length;
}
};原创内容 转载请注明出处
