一【題目類別】

• 哈希表

二【題目難度】

• 中等

三【題目編號】

• 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++語言版