题目描述
给定一个未排序的整数数组 nums，找出其中最长连续子序列的长度。要求时间复杂度为 O(n)。
示例
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长连续序列是 [1, 2, 3, 4]，长度为 4。
思路分析
核心思路是利用哈希集合存储所有元素，遍历每个元素时，仅检查其是否为连续序列的左边界（即不存在比它小1的元素）。若是左边界，则向右扩展，统计连续序列的长度。此方法确保每个元素最多被访问两次，时间复杂度为 O(n)。
代码实现
Java
class Solution {public int longestConsecutive(int[] nums) {//存储数组中所有元素Set<Integer> num_set = new HashSet<Integer>();for(int num : nums){num_set.add(num);}//res 最大连续子序列长度int longestStreak = 0;//遍历该集合for(int num : num_set){//判断该元素是否为左边界，如果num-1包含在集合中证明不是左边界，如果不在证明该元素为左边界if(!num_set.contains(num-1)){//找到左边界后，寻找右边界//记录当前值int currentNum = num;int currentStreak =1;//判断currentNum+1是否在集合中，如果在不为右边界，while(num_set.contains(currentNum+1)){//则+1 判断下一个在不在右边界currentNum +=1;//当前位置+1currentStreak +=1;}//直到不在集合中，证明到达了由边界，返回子序列长度longestStreak = Math.max(longestStreak, currentStreak);}}return longestStreak;}
}
Python
def longestConsecutive(nums):num_set = set(nums)longest = 0for num in num_set:if num - 1 not in num_set:current = numstreak = 1while current + 1 in num_set:current += 1streak += 1longest = max(longest, streak)return longest
C++
#include <unordered_set>
using namespace std;class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> num_set(nums.begin(), nums.end());int longest = 0;for (int num : num_set) {if (!num_set.count(num - 1)) {int current = num, streak = 1;while (num_set.count(current + 1)) {current++;streak++;}longest = max(longest, streak);}}return longest;}
};
Go
func longestConsecutive(nums []int) int {numSet := make(map[int]bool)for _, num := range nums {numSet[num] = true}longest := 0for num := range numSet {if !numSet[num-1] {current := numcurrentStreak := 1for numSet[current+1] {current++currentStreak++}if currentStreak > longest {longest = currentStreak}}}return longest
}
C（两种解法）
解法一：哈希集合（需 uthash 库）
#include <uthash.h>struct hash_table {int key;UT_hash_handle hh;
};int longestConsecutive(int* nums, int numsSize) {if (numsSize == 0) return 0;struct hash_table* set = NULL;for (int i = 0; i < numsSize; i++) {struct hash_table* tmp;int num = nums[i];HASH_FIND_INT(set, &num, tmp);if (!tmp) {tmp = malloc(sizeof(struct hash_table));tmp->key = num;HASH_ADD_INT(set, key, tmp);}}int longest = 0;struct hash_table *current, *tmp;HASH_ITER(hh, set, current, tmp) {int num = current->key;int prev = num - 1;struct hash_table* check;HASH_FIND_INT(set, &prev, check);if (!check) {int current_num = num, streak = 1;while (1) {int next = current_num + 1;HASH_FIND_INT(set, &next, check);if (check) {current_num = next;streak++;} else break;}if (streak > longest) longest = streak;}}// 清理哈希表HASH_ITER(hh, set, current, tmp) {HASH_DEL(set, current);free(current);}return longest;
}
解法二：排序（时间复杂度 O(n log n)）
int cmp(const void* a, const void* b) {return *(int*)a - *(int*)b;
}int longestConsecutive(int* nums, int numsSize) {if (numsSize == 0) return 0;qsort(nums, numsSize, sizeof(int), cmp);int max_streak = 1, current_streak = 1;for (int i = 1; i < numsSize; i++) {if (nums[i] != nums[i-1]) {if (nums[i] == nums[i-1] + 1) current_streak++;else {max_streak = fmax(max_streak, current_streak);current_streak = 1;}}}return fmax(max_streak, current_streak);
}
复杂度分析
- 时间复杂度：哈希集合解法为 O(n)，每个元素最多被访问两次。排序解法为 O(n log n)。
- 空间复杂度：哈希集合解法为 O(n)，用于存储元素集合。
通过哈希集合的巧妙运用，能够高效解决最长连续序列问题。不同语言的实现均遵循同一逻辑，确保了算法的高效性和一致性。