最长连续序列
- 给定一个未排序的整数数组 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
解题思路
- 首先，将数组中的所有元素存入一个集合（HashSet）中，方便进行快速查找。
- 然后，遍历数组中的每个元素，对于每个元素，检查其是否是一个序列的起始点，即判断其前一个数是否在集合中存在。
- 如果是起始点，则从该点开始向后查找连续序列的长度，直到找到序列的末尾。
- 更新最长连续序列的长度，并在遍历完成后返回结果。
具体步骤
- 将数组中的所有元素存入一个集合（HashSet）中。
- 遍历数组中的每个元素，对于每个元素执行以下步骤：
- 判断当前元素是否是一个序列的起始点，即判断其前一个数是否在集合中存在。
- 如果是起始点，则从该点开始向后查找连续序列的长度，直到找到序列的末尾。
- 更新最长连续序列的长度。
- 返回最长连续序列的长度。
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}
}
