leetcode 散列表 哈希算法 力扣128. 最长连续序列（哈希表）

Problem: 128. 最长连续序列

文章目录

题目描述思路复杂度Code

题目描述

思路

1.先将数组中的元素存入到一个set集合中（去除重复的元素） 2.欲找出最长连续序列（先定义两个int变量longestSequence和currentSequence用于记录最长连续序列和当前最长序列），我们可以在遍历给定数组时（当前遍历到的元素为nums[i]）去set集合中查找nums[i] - 1,是否存在；若存在，直接遍历下一个nums中的元素；若不存在则持续查找nums[i] + 1,是否存在于set集合中，若存在则更新currentSequence和longestSequence

复杂度

时间复杂度:

O

(

n

)

O(n)

O(n)；其中

n

n

n为数组nums的长度

空间复杂度:

O

(

n

)

O(n)

O(n)

Code

class Solution {

public:

/**

* Hash

*

* @param nums Given array

* @return int

*/

int longestConsecutive(vector& nums) {

unordered_set set;

// Save data to set to achieve deduplication

for (int i = 0; i < nums.size(); ++i) {

set.insert(nums[i]);

}

int longestSequence = 0;

for (const auto& num : set) {

// If num-1 does not exist in set

if (!set.count(num - 1)) {

int currentNum = num;

int currentSequence = 1;

// Find num + 1.....

while (set.count(currentNum + 1)) {

currentNum += 1;

// Add one to the current currentSequence

currentSequence += 1;

}

longestSequence = max(currentSequence, longestSequence);

}

}

return longestSequence;

}

};

相关链接