原题
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2] 输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
解法
思想
哈希集，先遍历一遍存储每个数字是否出现过，第二遍遍历找到一个连续序列的头（没有等于这个值-1的元素）计算这个连续序列的长度，并存储下最大值
代码
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) set.add(num);
int maxLen = 0;
for (int num : nums) {
if (!set.contains(num - 1)) {
int curNum = num;
int curLen = 1;
while (set.contains(curNum + 1)) {
curNum += 1;
curLen += 1;
}
maxLen = Math.max(maxLen,curLen);
}
}
return maxLen;
}
}
func longestConsecutive(nums []int) int {
numMap := map[int]bool{}
for _, num := range nums{
numMap[num] = true
}
ans := 0
for _, num := range nums{
// 只遍历一个连续序列的头
if !numMap[num-1]{
cur := 1
temp := num
for numMap[temp+1]{
cur ++
temp ++
}
ans = max(ans, cur)
}
}
return ans
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode128-%e6%9c%80%e9%95%bf%e8%bf%9e%e7%bb%ad%e5%ba%8f%e5%88%97/
