leetcode hot100 第三题：最长连续序列（Java）

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

方法一：HashSet【时间复杂度：O(n)】

优化：

1.直接遍历查找改为哈希表查找，时间复杂度为O(1)

2.对一个连续序列中的元素进行删减，让其只在最小的元素才开始+1遍历，避免重复遍历

代码：

class Solution {   //方法一：HashSet

    public int longestConsecutive(int[] nums) {

        // 建立一个存储所有数的哈希表，同时起到去重功能

        Set<Integer> hashset = new HashSet<>();

        for(int num : nums){

            hashset.add(num);

        }

        int ans = 0;   // 存储最长连续序列的长度

        // 遍历去重后的所有数字

        for(int num : hashset){

            int cur = num;

            // 只有当num-1不存在时，才开始向后遍历num+1，num+2，num+3......

            if(!hashset.contains(cur - 1)){

                while(hashset.contains(cur + 1)){

                    cur++;

                }

            }

            ans = Math.max(ans, cur - num + 1);

        }

        return ans;

    }

}