自学力扣：最长连续序列

给定一个未排序的整数数组 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

示例 3：

输入：nums = [1,0,1,2]

输出：3

方法一、排序

class Solution {public int longestConsecutive(int[] nums) {// 1. 处理空数组：如果数组长度为0，直接返回0（没有任何序列）if(nums.length == 0) return 0;// 2. 排序数组：把数组按从小到大排序Arrays.sort(nums);  // 示例1排序后：[1,2,3,4,100,200]// 3. 初始化变量int ans = 0;       // 存储最终的最长序列长度（结果）int tmp = 1;       // 临时记录当前连续序列的长度（至少为1，因为单个元素也是序列）// 4. 遍历排序后的数组（从第2个元素开始，和前一个对比）for(int i = 1; i < nums.length; i++){// 情况1：当前元素和前一个元素相同（比如[1,1,2]中的两个1）if(nums[i] == nums[i-1]){continue;  // 跳过，不影响连续序列长度（相同数字不算新元素）}// 情况2：当前元素比前一个元素大1（连续的情况）else if(nums[i] == nums[i-1] + 1){tmp++;     // 当前序列长度+1（比如4和3差1，tmp从3→4）}// 情况3：当前元素和前一个元素不连续（比如100和4差96）else{// 更新最长序列长度（取当前最长ans和临时tmp的最大值）ans = Math.max(ans, tmp);  tmp = 1;  // 重置临时长度（开始新的序列）}}// 5. 最后一次比较：循环结束后，可能最后一个序列还没更新到ans中return Math.max(ans, tmp);}
}

方法二、哈希表

class Solution {public int longestConsecutive(int[] nums) {// 1. 创建一个哈希集合（Set），用于存储数组中的所有数字//    作用1：自动去重（比如数组里有重复的1，Set里只会存一个1）//    作用2：支持 O(1) 时间复杂度的查询（快速判断某个数字是否存在）Set<Integer> numSet = new HashSet<>();// 把数组里的所有数字添加到Set中for (int num : nums) {numSet.add(num);}// 2. 定义变量记录最长连续序列的长度，初始为0（如果数组为空，直接返回0）int longestStreak = 0;// 3. 遍历Set中的每个数字（因为去重了，避免重复处理相同数字）for (int num : numSet) {// 关键判断：只有当「当前数字-1」不在Set中时，才把它作为连续序列的起点// 举例：如果数字是2，且1存在，说明2不是起点（起点是1），直接跳过//      如果数字是1，且0不存在，说明1是起点（从1开始往后找连续数字）if (!numSet.contains(num - 1)) {// 记录当前起点数字int currentNum = num;// 记录当前连续序列的长度（至少为1，因为起点本身就是一个数字）int currentStreak = 1;// 4. 从起点开始，向后查找连续的数字//    只要「当前数字+1」存在于Set中，就说明序列可以延长while (numSet.contains(currentNum + 1)) {// 移动到下一个连续数字（比如从1→2，从2→3）currentNum += 1;// 连续序列长度+1（比如1→2后，长度从1变成2）currentStreak += 1;}// 5. 更新最长序列长度：取「目前最长长度」和「当前序列长度」的较大值longestStreak = Math.max(longestStreak, currentStreak);}}// 6. 返回最长连续序列的长度return longestStreak;}
}