传送门:https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked

题意就是让我们找出最长的连续序列（不要求元素在原数组连续）

首先可以想到暴力查找即不断搜索整个数组看有没有下一个，当然这样时间复杂度肯定很大不符合要求。

其次可以用排序的方法先将数组排成有顺序的再查找，这样时间复杂度是$O(nlogn)$。

进一步思考，我们在查找下一个时可以用hash表来查询，这样的时间复杂度是$O(1)$的，但是极限情况下的总时间复杂度还是会达到$O(n)$。但是，我们发现，我们枚举$x$的情况，是因为他是连续序列的第一个，即$x-1$不存在这个序列中，因为如果存在的话，序列的第一个就是$x-1$了，故我们只需要在第二层枚举前判断一下$x-1$是否存在即可。

参考代码:

/**
 * problem ：LeetCode128. 最长连续序列
 * date : 2025/3/20 20:01
 */
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> list = new HashSet<>();
        for (int num : nums) {
            list.add(num);
        }
        int ans = 0;
        for (int now : list) {
            if (!list.contains(now - 1)) {
                int y = now;
                while (list.contains(y + 1)) {
                    y++;
                }
                ans = Math.max(ans, y - now + 1);
            }
        }
        return ans;
    }
}

时间复杂度:这样做的话内存循环每个数只会进入一次，因为他只可能有一次机会作为序列第一个数，然后进入内循环，其他情况会被特判掉，故这个时间复杂度是$O(n)$。