新手搭建网站教程关键词查网址
LeetCode哈希表：最长连续序列
题目描述
给定一个未排序的整数数组 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
解题思路
首先想到的方法就是先排序，然后再找到符合条件序列，但这样的话复杂度就不符合题目要求。最好的排序的是nlogn因此排序这条路走不通，考虑采用哈希，哈希的一个优点就是寻找元素容易，那就考虑怎么去找这个元素，两种方案，
- 第一种：找到一个序列最小值再以此向大的进行判断
- 第二种：找到一个序列最大的向小的方向判断
最后再返回最长长度
步骤如下：
- 创建HashSet：首先，创建一个
HashSet，用于存储数组中的元素。HashSet的目的是为了快速检查数组中是否包含某个元素，以及在O(1)时间内添加元素。 - 将数组元素加入HashSet：遍历输入数组
nums，将每个元素加入HashSet。 - 寻找连续序列：对于每个元素
num，检查是否存在num - 1，如果不存在，说明num可能是一个连续序列的起点。然后，从num开始，通过不断检查num + 1是否在HashSet中，来找到连续序列的长度。 - 更新最长连续序列的长度：在每次找到一个连续序列后，更新最长连续序列的长度。
- 返回结果：返回最终找到的最长连续序列的长度。
代码
public class hash2 {public int longestConsecutive(int[] nums) {HashSet<Integer> set=new HashSet<>();for (int num : nums) {set.add(num);}int ans=0;for (int num : set) {int right=num;if (!set.contains(right - 1)) {while (set.contains(right+1))right++;}ans=Math.max(ans,right-num+1);}return ans;}public static void main(String[] args) {hash2 ha=new hash2();System.out.println(ha.longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}));}
}
优化以及其他思想的方法
- 方法1 哈希集合（最普遍也最简单的思路，必须掌握）
- 方法2 哈希表（思路1的进阶）
- 方法3 动态规划（极其巧妙，推荐掌握）
- 方法4 并查集（建议掌握）
传送：迪迦~~