Crack LeetCode 之 128. Longest Consecutive Sequence

本文主要是介绍Crack LeetCode 之 128. Longest Consecutive Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://leetcode.com/problems/longest-consecutive-sequence/

解题思路是，建立一个哈希表，然后loop整个集合，对于每个数字可以通过查询哈希表检查其周边的数字是否连续；如果连续的话则保存最大的连续长度，并且将该数字从哈希表中删除。最大的连续长度就是结果。该算法的时间复杂度为O(n)，空间复杂度也是O(n)。

c++代码如下：

class Solution {
public:int longestConsecutive(vector<int>& nums) {set<int> numSet;for (auto i : nums)numSet.insert(i);int maxLen = 0;for (auto i : nums) {int res = 0;int resl = i-1;int resr = i;while (numSet.find(resl) != numSet.end()) {res++;numSet.erase(resl--);}while (numSet.find(resr) != numSet.end()) {res++;numSet.erase(resr++);}if (res > maxLen)maxLen = res;}return maxLen;}
};

python代码如下：

class Solution:def longestConsecutive(self, nums):numSet = {}for item in nums:numSet[item] = 1maxLen = 0for item in nums:res = 0resl = item - 1resr = itemwhile resl in numSet:numSet.pop(resl, None);res = res + 1resl = resl - 1while resr in numSet:numSet.pop(resr, None);res = res + 1resr = resr + 1if (res > maxLen):maxLen = resreturn maxLen

 

这篇关于Crack LeetCode 之 128. Longest Consecutive Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---