LeetCode128最长连续序列
Contents
题目
给定一个未排序的整数数组 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.对int数组(int[] nums)进行排序可以使用Arrays.sort(nums)，这个方法会直接操作nums变成升序排列
2.nums的长度使用nums.length获取
3.hashmap查找key、value使用方法，map.containsKey和map.containsValue，set使用set.contains
题解
public int longestConsecutive(int[] nums) {
Set<Integer> numSet = new HashSet<>();
for (int num : nums){
numSet.add(num);
}
int longestStreak = 0;
for(Integer num : numSet){
if(!numSet.contains(num - 1)){
Integer numTemp = num;
int current = 1;
while (numSet.contains(numTemp + 1)){
numTemp++;
current++;
}
longestStreak = Math.max(longestStreak, current);
}
}
return longestStreak;
}
重点是num-1这里，避免了重复处理已经处理过的数据