当前位置：首页 > article >正文

力扣100题之128. 最长连续序列

article 2025/8/25 7:08:15

方法1 使用了hash

方法思路
使用哈希集合：首先将数组中的所有数字存入一个哈希集合中，这样可以在 O(1) 时间内检查某个数字是否存在。
寻找连续序列：遍历数组中的每一个数字，对于每一个数字，
检查它是否是某个连续序列的起点（即检查 num - 1 是否存在于集合中）。
如果不是起点，则跳过；
如果是起点，则开始向后检查连续的数字（num + 1, num + 2 等），并记录序列的长度。
更新最大长度：在遍历过程中，不断更新记录的最大序列长度。
这种方法确保每个数字最多被访问两次（一次在遍历数组时，一次在检查连续序列时），因此时间复杂度为 O(n)。

    public int longestConsecutive(int[] nums) {/*  方法思路使用哈希集合：首先将数组中的所有数字存入一个哈希集合中，这样可以在 O(1) 时间内检查某个数字是否存在。寻找连续序列：遍历数组中的每一个数字，对于每一个数字，检查它是否是某个连续序列的起点（即检查 num - 1 是否存在于集合中）。如果不是起点，则跳过；如果是起点，则开始向后检查连续的数字（num + 1, num + 2 等），并记录序列的长度。更新最大长度：在遍历过程中，不断更新记录的最大序列长度。这种方法确保每个数字最多被访问两次（一次在遍历数组时，一次在检查连续序列时），因此时间复杂度为 O(n)。*///        1.哈希集合初始化：将数组中的所有数字存入哈希集合 numSet 中，以便快速查找。Set<Integer> hashSet = new HashSet<>;for(int num:nums){hashSet.add(num);}int longesetStreak = 0;
//        2.遍历集合：对于集合中的每一个数字，检查它是否是某个连续序列的起点（即 num - 1 不在集合中）。for(int num:hashSet){//        3.扩展序列：如果是起点，则向后扩展序列，计算当前连续序列的长度 currentStreak。if(!hashSet.contains(num-1)){int currentNum =num;int currentStreak=1;while(hashSet.contains(currentNum+1)){currentNum++;currentStreak++;}//        4.更新最大值：比较并更新最长序列长度 longestStreak。longesetStreak=Math.max(longesetStreak,currentStreak);}}//        5.返回结果：最终返回最长序列的长度。return longesetStreak;}

方法二排序法（时间复杂度大）

public int longestConsecutive(int[] nums) {// 处理边界情况：空数组直接返回0if (nums.length == 0) return 0;// 对数组排序（升序），便于后续连续元素判断Arrays.sort(nums);int maxLength = 0;  // 记录最长连续子序列长度int currentLength = 1;  // 当前连续子序列长度，初始为1（至少有一个元素）// 从第二个元素开始遍历（索引1到末尾）for (int i = 1; i < nums.length; i++) {int currentNum = nums[i];int prevNum = nums[i - 1];if (currentNum == prevNum) {// 跳过重复元素（排序后相邻重复，不影响连续性判断）continue;} else if (currentNum == prevNum + 1) {// 当前元素与前一个元素连续，长度加1currentLength++;} else {// 连续序列中断，更新最长长度，并重置当前长度maxLength = Math.max(maxLength, currentLength);currentLength = 1;}}// 处理最后一次连续序列（遍历结束后可能还有未比较的长度）return Math.max(maxLength, currentLength);
}