最长连续序列

最长连续序列（Longest Consecutive Sequence）要求在给定的未排序整数数组中，找出最长的连续序列（可以是递增或递减），并返回其长度。

import java.util.HashSet;

public class LongestConsecutiveSequence {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int longestStreak = 0;

        // 先将所有数字存入HashSet中，方便快速查找
        for (int num : nums) {
            set.add(num);
        }

        // 遍历数组中的每个数字
        for (int num : nums) {
            // 如果当前数字是某个连续序列的起点（即前一个数字不在HashSet中）
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                // 继续检查当前数字之后的数字是否在HashSet中，直到找到不在的为止
                while (set.contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }

                // 更新最长连续序列的长度
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

解释每一步：

我们首先使用HashSet将给定的整数数组存储起来，这样可以快速地判断一个数字是否在数组中。
接下来，我们遍历数组中的每个数字。
对于每个数字，我们检查它是否是某个连续序列的起点（即前一个数字不在HashSet中）。
如果是起点，我们从当前数字开始，一直向后查找连续的数字，直到找到不在HashSet中的数字为止，这个过程中记录连续序列的长度。
更新最长连续序列的长度。
最后，返回最长连续序列的长度。

这种解法的时间复杂度为O(n)，其中n为数组的长度，因为我们只需遍历一次数组。空间复杂度也为O(n)，因为需要使用HashSet来存储数组中的元素。