【哈希】Leetcode 128. 最长连续序列 【中等】

最长连续序列

• 给定一个未排序的整数数组 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]
• �index.php/tags-41973.html" >��出：9

  解题思路

  1. 首先，将数组中的所有元素存入一个集合（HashSet）中，方便进行快速查找。
  2. 然后，遍历数组中的每个元素，对于每个元素，检查其是否是一个序列的起始点，即判断其前一个数是否在集合中存在。
  3. 如果是起始点，则从该点开始向后查找连续序列的长度，直到找到序列的末尾。
  4. 更新最长连续序列的长度，并在遍历完成后返回结果。

  具体步骤

  1. 将数组中的所有元素存入一个集合（HashSet）中。
  2. 遍历数组中的每个元素，对于每个元素执行以下步骤：
     • 判断当前元素是否是一个序列的起始点，即判断其前一个数是否在集合中存在。
     • 如果是起始点，则从该点开始向后查找连续序列的长度，直到找到序列的末尾。
     • 更新最长连续序列的长度。
     • 返回最长连续序列的长度。

  java实现

  public class LongestConsecutiveSequence {    public int longestConsecutive(int[] nums) {        if (nums == null || nums.length == 0) {            return 0;        }        // 将数组元素放入 HashSet 中，以便快速查找        HashSet numSet = new HashSet();        for (int num : nums) {            numSet.add(num);        }        int longestStreak = 0;        // 遍历数组元素        for (int num : nums) {            // 如果当前元素是一个序列的起点，即前一个数字不存在于 HashSet 中            if (!numSet.contains(num - 1)) {                int currentNum = num;                int currentStreak = 1;                // 继续查找连续的数字                while (numSet.contains(currentNum + 1)) {                    currentNum++;                    currentStreak++;                }                // 更新最长序列的长度                longestStreak = Math.max(longestStreak, currentStreak);            }        }        return longestStreak;    }    public static void main(String[] args) {        LongestConsecutiveSequence solution = new LongestConsecutiveSequence();        int[] nums1 = {100, 4, 200, 1, 3, 2};        System.out.println(solution.longestConsecutive(nums1)); // 输出：4        int[] nums2 = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};        System.out.println(solution.longestConsecutive(nums2)); // 输出：9    }}

  （）（）