【哈希】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]
• 输出：9

解题思路

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

具体步骤

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

java实现

public class LongestConsecutiveSequence {public int longestConsecutive(int[] nums) {if (nums == null || nums.length == 0) {return 0;}// 将数组元素放入 HashSet 中，以便快速查找HashSet<Integer> 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)); // 输出：4int[] nums2 = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};System.out.println(solution.longestConsecutive(nums2)); // 输出：9}
}