据说是字节跳动二面的原题,这题面试要是让我当场手撕,我直接当场去世T_T
给定一个未排序的整数数组 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
提示:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
思路
题目的意思是让我们找出这个数组里面有多少个是连续,还要在O(n)的复杂度实现
所以我们只能进行一层循环
先铺垫一下思路,一个数可能是一个连续序列的开始,也可能是一个连续序列的结束,还有可能连接起左右两个连续序列形成一个新的序列,序列长度即为left+1+right,基于此,下面开始讲解
我们的思路是这样的,建立起一个哈希映射,一层循环遍历数组元素,判断这个元素在不在哈希映射表里面,如果不在,我们把这个元素添加到哈希映射里面去,并设置值为1,表示这个连续序列的长度为1
接着判断这个元素减一,即x-1,在不在哈希里面,我们想要看这个元素x是不是一个连续序列的尾巴,如果是,让元素x的值为x-1的值加一,表示这个连续的序列现在又多了一个,但是这样还不行,我们必须把这个序列的另一端,即这个连续序列的头部的值也更新一下,因此我们需要先记录下这个头部的索引,为什么不直接更新呢,因为元素x可能还可以连接起右边的序列使得目前的连续序列变长,因此我们先记录下序列头部的索引,后面再一起更新
然后就是判断x+1在不在哈希里面,看看x是不是一个连续序列的头部,如果是,我们就可以更新这个连续序列的长度,和上面一样,我们同时需要更新另一端,即这个序列的尾巴的值也更新为新序列的长度
在过程中,更新最长的长度
class Solution {
public:
int longestConsecutive(vector<int> &nums) {
unordered_map<int, int> hashmap;
int answer = 0;
for (int num: nums) {
if (hashmap.find(num) == hashmap.end()) {
hashmap[num] = 1;
int left = num;
int right = num;
if (hashmap.find(num - 1) != hashmap.end()) {
hashmap[num] = hashmap[num - 1] + 1;
left=num - hashmap[num-1];
}
if (hashmap.find(num + 1) != hashmap.end()) {
hashmap[num] = hashmap[num + 1] + hashmap[num];
right=num + hashmap[num+1];
}
hashmap[left] = hashmap[right] = hashmap[num];
answer = answer > hashmap[num] ? answer : hashmap[num];
}
}
return answer;
}
};