leetCode-128:Longest Consecutive Sequence

问题描述

给定一个整数数组,要求在 O(n) 的时间复杂度内找出数组中最长连续序列的元素个数。题目链接:点我

样例输入输出

输入:[100, 4, 200, 1, 3, 2]

输出:4

说明:最长连续序列为 1 2 3 4,序列中元素个数为 4

输入:[1, 2, 3, 4, 6, 7, 8, 9, 10]

输出:5

说明:最长连续序列为 6 7 8 9 10,序列中元素个数为 5

问题解法

遍历数组,将数组中每个元素放在 map 中,然后重新遍历数组中每个元素,以该元素为起点,每次加一,看新的数字是否在 map 中,如果在,则说明新的数字存在数组,同时也说明这个新的数字与当前元素是能构成连续序列的,如果不在,则说明新的数字不在数组中,结束循环。同样,以该元素为终点,每次减一,重复上述步骤,直到条件不满足为止。这样就能找出包含当前元素的最长序列的起始和终止的数字,进而获取到包含当前元素的最长序列的元素个数。在循环遍历数组时,每次比较最长序列的元素个数,取其最大值,当数组遍历完成时,变量保存的最大值就是求解的值。代码如下

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution
{
public int longestConsecutive(int[] nums)
{
Map<Integer, Boolean> map = new HashMap<>(nums.length);
for (int num : nums)
{
map.put(num, false);
}

int maxCount = 0;
for (int num : nums)
{
int count = 0;
if (!map.get(num))
{
count++;
int next = num + 1;
while (!map.getOrDefault(next, true))
{
map.put(next, true);
count++;
next = next + 1;
}

int front = num - 1;
while (!map.getOrDefault(front, true))
{
map.put(front, true);
count++;
front = front - 1;
}

if (count > maxCount)
{
maxCount = count;
}
}
}

return maxCount;
}
}