最长连续序列
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
1 2 3
| 输入:nums = [100,4,200,1,3,2] 输出:4 解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
|
思路: 可以直接排序,然后每一个节点看是否存在(累加一直到不存在).但题目要求时间复杂度O(n).所以采用hash优化的方式
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| class Solution { public int longestConsecutive(int[] nums) { int max = 0; Set<Integer> set = new HashSet(); for(int num : nums) { set.add(num); } for(int num : nums) { int tmp = num; int count = 0; if(set.contains(tmp-1)){ continue; } while(set.contains(tmp)){ count++; tmp++; } max = Math.max(max, count); } return max; } }
|