力扣经典150题第四十六题：最长连续序列

用户8589624

发布于 2025-11-13 16:09:11

560

文章被收录于专栏：nginxnginx

力扣经典150题第四十六题：最长连续序列

介绍

在本文中，我们将解决力扣经典150题中的第四十六题，该题目要求我们在未排序的整数数组中找出数字连续的最长序列的长度。我们将设计并实现时间复杂度为 O(n) 的算法解决此问题。

题目分析

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

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

示例 1：

输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9

提示：

0 <= nums.length <= 105 -109 <= nums[i] <= 109

解题思路

我们可以使用哈希表来解决这个问题。具体来说，我们首先将数组中的所有元素放入哈希表中。然后，我们遍历数组中的每个元素，在遍历的过程中，对于每个元素，我们检查其前一个数字是否在哈希表中，如果存在，则将当前数字加入连续序列中，并继续检查下一个数字。最终，我们可以得到最长的连续序列的长度。

算法实现

import java.util.HashSet;

public class Solution {
    public int longestConsecutive(int[] nums) {
        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++;
                    currentStreak++;
                }
                
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        
        return longestStreak;
    }
}

复杂度分析

时间复杂度：O(n)，其中n是数组的长度。我们需要遍历数组两次，一次用于填充哈希表，另一次用于计算最长序列的长度。
空间复杂度：O(n)，哈希表最多存储n个元素。

实例与测试

除了题目中给出的示例外，我们还可以进行更多的测试以验证算法的正确性和效率。例如：

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {100, 4, 200, 1, 3, 2};
        int[] nums2 = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
        
        System.out.println(solution.longestConsecutive(nums1)); // 输出：4
        System.out.println(solution.longestConsecutive(nums2)); // 输出：9
    }
}

通过这些示例测试，我们可以确保算法能够正确地处理各种情况，并在给定的时间复杂度内完成任务。