这道题要求的是O(n)的时间复杂度,我们先将数组存入哈希表中,再遍历每一个数,判断其是不是连续序列中的起点(即判断num-1在不在哈希表中),如果是起点,就用一个while循环判断每一个起点的最长连续序列长度(即判断num+1在不在哈希表中),最后删除掉已经在连续序列中遍历过的数字。
class Solution {
public int longestConsecutive(int[] nums) {
int res = 0;
Set<Integer> set = new HashSet<>();
for (int num : nums) set.add(num);
for (int begin : nums) {
if (!set.contains(begin - 1)) {
set.remove(begin);
int end = begin;
while (set.contains(++end)) {
set.remove(end);
}
res = Math.max(res, end - begin);
}
}
return res;
}
}
记录这道题除了想要记录这个思路外,还想记录一点,就是O(n)的时间复杂度并不一定说明只能有一层循环,也可以是多层循环,例如这里的for + while,只要保证每一个数只被遍历一遍即可。这里的边遍历边删除就避免了一个数字被遍历多次,也从而保证了O(n)的时间复杂度。