寻找最长连续序列

题解思路

本题的目标是找到数组中最长的连续整数序列，并且要求算法的时间复杂度为 $O(n)$。可以使用 哈希集合（HashSet） 来实现高效查找，从而避免排序带来的 $O(n \log n)$ 复杂度。

解题方法

方法：哈希表 + 贪心

1. 构建哈希集合

   • 由于查找某个元素是否存在的操作在哈希表中是 $O(1)$ 复杂度，因此可以使用 set 存储数组中的所有数，方便后续查询。

2. 遍历数组，寻找连续序列的起点

   • 对于每个数字 num，如果 num - 1 不在哈希集合中，则 num 是一个序列的起点。
   • 以该 num 为起点，不断检查 num + 1, num + 2, ... 是否存在于集合中，计算序列的长度。

3. 记录最大序列长度

   • 通过遍历所有可能的起点，不断更新最长序列长度。

时间复杂度分析

• 构建哈希集合：$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;
}

Leetcode 3.最长连续序列-原题链接

题目内容

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

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

输入描述

输入共两行。

• 第一行为两个个整数$n$，代表数组$nums$的长度。

• 第二行为$n$个整数$nums_0,nums_1,...,nums_{n-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 <= 10^5$

• $-10^9 <= nums[i] <= 10^9$