LeetCode——最长连续序列

NO.128 最长连续序列困难

思路一：比较排序 比较排序，然后遍历。

public int longestConsecutive(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    //排序O(nlogn)
    Arrays.sort(nums);
    int curStreak = 1;
    int longestStreak = 1;
    for (int i = 1; i < nums.length; i++) {
        //跳过重复元素
        if (nums[i] != nums[i - 1]) {
            //计算连续序列长度
            if (nums[i] == nums[i - 1] + 1) {
                curStreak++;
            } else {
                longestStreak = Math.max(longestStreak, curStreak);
                curStreak = 1;
            }
        }
    }
    //求max，防止最后一组连续序列被遗漏
    return Math.max(longestStreak, curStreak);
}

但是时间O(nlogn)

思路二：哈希表改进暴力法 先看一个O(n^3)的暴力：

public int longestConsecutive(int[] nums) {
    int longestStreak = 0;
    //遍历
    for (int num : nums) {
        int cur = num;
        int curStreak = 1;
        //计算num开头的连续序列长度
        while (isContains(nums, cur + 1)) {
            cur++;
            curStreak++;
        }
        //更新最长长度
        longestStreak = Math.max(longestStreak, curStreak);
    }
    return longestStreak;
}

private boolean isContains(int[] nums, int num) {
    //遍历
    for (int i : nums) {
        if (i == num) return true;
    }
    return false;
}

开始优化：用 HashSet 存储 nums ，去重的同时确保isContains操作时 O(1) 复杂度。

暴力还有一个问题就是要将每个 num 都作为连续序列的开头分别进行一次遍历计算。针对这一点，我们只需要将 num-1不在 nums 中的 num 作为连续序列的开头计算一次长度即可！(有点拗口，但是不难理解)

因为 num 后序的其他数字一定已经出现在了某个序列里，我们要避免重复计算。

public int longestConsecutive(int[] nums) {
    //nums存入HashSet
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }
    int longestStreak = 0;
    for (Integer num : set) {
        //num-1不存在的num作为序列的开头
        if (!set.contains(num - 1)) {
            int cur = num;
            int curStreak = 1;
            //num+1是否存在
            while (set.contains(cur + 1)) {
                cur++;
                curStreak++;
            }
            longestStreak = Math.max(longestStreak, curStreak);
        }
    }
    return longestStreak;
}

时间复杂度：O(n) 虽然是 for 里嵌套了 while ，但是因为if (!set.contains(num - 1))(原因在优化时说过了)，所以实际执行时间是O(n+n)。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.128 最长连续序列 困难

NO.128 最长连续序列困难