#P4002. 最长连续序列
-
ID: 2204
Tried: 948
Accepted: 330
Difficulty: 4
最长连续序列
题目内容
给定一个未排序的整数数组nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为O(n)的算法解决此问题。
输入描述
输入共两行。
-
第一行为两个个整数n，代表数组nums的长度。
-
第二行为n个整数nums0,nums1,...,numsn−1，数字之间以空格分隔。
输出描述
输出一个整数，代表答案。
样例1
输入
6
100 4 200 1 3 2
输出
4
说明
最长数字连续序列是 [1,2,3,4]。它的长度为4。
样例2
输入
10
0 3 7 2 5 8 4 6 0 1
输出
9
样例3
输入
4
1 0 1 2
输出
3
提示
-
0<=nums.length<=105
-
−109<=nums[i]<=109
寻找最长连续序列
题解思路
本题的目标是找到数组中最长的连续整数序列，并且要求算法的时间复杂度为 O(n)。可以使用 哈希集合（HashSet） 来实现高效查找，从而避免排序带来的 O(nlogn) 复杂度。
解题方法
方法：哈希表 + 贪心
-
构建哈希集合
- 由于查找某个元素是否存在的操作在哈希表中是 O(1) 复杂度，因此可以使用
set存储数组中的所有数，方便后续查询。
- 由于查找某个元素是否存在的操作在哈希表中是 O(1) 复杂度，因此可以使用
-
遍历数组，寻找连续序列的起点
- 对于每个数字
num，如果num - 1不在哈希集合中，则num是一个序列的起点。 - 以该
num为起点，不断检查num + 1, num + 2, ...是否存在于集合中，计算序列的长度。
- 对于每个数字
-
记录最大序列长度
- 通过遍历所有可能的起点，不断更新最长序列长度。
时间复杂度分析
- 构建哈希集合：O(n)
- 遍历数组：O(n)
- 查找连续序列：O(n)（每个元素最多只会被访问两次）
- 总时间复杂度：O(n)
代码实现
以下是 Python、Java、C++ 三种语言的实现，均采用 HashSet 进行优化。
Python 实现
class Solution:
def longestConsecutive(self, nums):
if not nums:
return 0
num_set = set(nums) # 将数组存入哈希集合
longest_streak = 0
for num in num_set:
if num - 1 not in num_set: # 只有当 num 是起点时才进入
current_num = num
current_streak = 1
while current_num + 1 in num_set: # 计算序列长度
current_num += 1
current_streak += 1
longest_streak = max(longest_streak, current_streak) # 更新最大长度
return longest_streak
# 输入处理
if __name__ == "__main__":
n = int(input().strip())
nums = list(map(int, input().split()))
solution = Solution()
print(solution.longestConsecutive(nums))
Java 实现
import java.util.HashSet;
import java.util.Scanner;
public class Main {
public class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
HashSet<Integer> numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num); // 将数组存入哈希集合
}
int longestStreak = 0;
for (int num : numSet) {
if (!numSet.contains(num - 1)) { // 只有起点才进入
int currentNum = num;
int currentStreak = 1;
while (numSet.contains(currentNum + 1)) { // 计算连续序列
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
scanner.close();
Main main = new Main();
Solution solution = main.new Solution();
System.out.println(solution.longestConsecutive(nums));
}
}
C++ 实现
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if (nums.empty()) return 0;
unordered_set<int> numSet(nums.begin(), nums.end()); // 存入哈希集合
int longestStreak = 0;
for (int num : numSet) {
if (numSet.find(num - 1) == numSet.end()) { // 只有起点才进入
int currentNum = num;
int currentStreak = 1;
while (numSet.find(currentNum + 1) != numSet.end()) { // 计算连续序列
currentNum += 1;
currentStreak += 1;
}
longestStreak = max(longestStreak, currentStreak);
}
}
return longestStreak;
}
};
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
Solution solution;
cout << solution.longestConsecutive(nums) << endl;
return 0;
}