【LeetCode每日一题】——128.最长连续序列

一【题目类别】

• 哈希表

二【题目难度】

• 中等

三【题目编号】

• 128.最长连续序列

四【题目描述】

• 给定一个未排序的整数数组 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<=10^5$
• $-10^9<=nums[i]<=10^9$

七【解题思路】

• 利用哈希表的思想
• 首先将数组中的元素加入哈希表中，这么做的目的是去重，并且为了方便后续的计算
• 然后遍历哈希表中的每个元素，计算从这个元素开始的连续数组，通过哈希表进行扫描就可以
• 这样我们就只使用了$O(n)$的时间复杂度解决这个问题
• 最后返回结果即可

八【时间频度】

• 时间复杂度：$O(n)$，$n$为传入的数组的长度
• 空间复杂度：$O(n)$，$n$为传入的数组的长度

九【代码实现】

1. Java语言版

class Solution {public int longestConsecutive(int[] nums) {HashSet<Integer> map = new HashSet<>();for(int i = 0;i < nums.length;i++){map.add(nums[i]);}int res = 0;for(int num : map){if(!map.contains(num - 1)){int curNum = num;int curLen = 1;while(map.contains(curNum + 1)){curNum += 1;curLen += 1;}res = Math.max(res, curLen);}}return res;}
}

2. C语言版

struct HashNode
{int key;UT_hash_handle hh;
};int longestConsecutive(int* nums, int numsSize)
{struct HashNode* map = NULL;struct HashNode* tempNode = NULL;for(int i = 0;i < numsSize;i++){HASH_FIND_INT(map, &nums[i], tempNode);if(tempNode == NULL){struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));newNode->key = nums[i];HASH_ADD_INT(map, key, newNode);}}struct HashNode *val, *temp;int res = 0;HASH_ITER(hh, map, val, temp){if(val != NULL){int lastVal = val->key - 1;HASH_FIND_INT(map, &lastVal, tempNode);if(tempNode == NULL){int curNum = val->key + 1;int curLen = 1;HASH_FIND_INT(map, &curNum, tempNode);while(tempNode != NULL){curNum += 1;curLen += 1;HASH_FIND_INT(map, &curNum, tempNode);}res = fmax(res, curLen);}}}HASH_ITER(hh, map, val, temp){HASH_DEL(map, val);free(val);}return res;
}

3. Python语言版

class Solution:def longestConsecutive(self, nums: List[int]) -> int:map = set(nums)res = 0for num in map:if num - 1 not in map:curNum = numcurLen = 1while curNum + 1 in map:curNum += 1curLen += 1res = max(res, curLen)return res

4. C++语言版

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> map;for(int i = 0;i < nums.size();i++){map.insert(nums[i]);}int res = 0;for(const int& num : map){if(!map.count(num - 1)){int curNum = num;int curLen = 1;while(map.count(curNum + 1)){curNum += 1;curLen += 1;}res = max(res, curLen);}}return res;}
};

十【提交结果】

1. Java语言版
   

2. C语言版
   

3. Python语言版
   

4. C++语言版