字節阿裏員工互懟，網友：五十步笑百步。。

網上一字節網友發帖： 公司能不能少招點阿裏人 ，下面一位阿裏的員工回復到： 公司能不能少招點字節人 。阿裏味，字節範，相互看不順眼。

有網友評論說：真是五十步笑百步，阿裏味太裝了，而且天天整合整合，拉齊拉齊，真是服了。字節這邊就是卷，毫無意義的卷。

--------------下面是今天的演算法題--------------

來看下今天的演算法題，這題是LeetCode的第128題：最長連續序列。

問題描述

來源：LeetCode第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

問題分析

這題讓找出 數位連續的最長序列 ，我們很容易想到先對陣列進行排序，然後尋找，但題中要求時間復雜度是 O(n) ，排序的時間復雜度最低也是 O(nlogn) ，不符合要求。

數位連續的序列肯定有個 起始值 ，我們只需要從起始值開始尋找即可，比如序列[3,2,4,1]，數位 3 前面有 2 ，所以它肯定不是連續序列的起始值，同理數位 2,4 也都不是，只有數位 1 是起始值，因為數位 1 前面沒有數位 0 ，所以只需要從數位 1 開始尋找即可。

也就是說如果當前數位前面還有相鄰的數位，那麽當前數位就不可能是起始值，這裏怎麽判斷當前數位前面還有沒有相鄰的數位呢？我們可以提前把陣列中的元素全部放到集合set中，判斷的時候只需要從set中尋找即可。

JAVA：

publicintlongestConsecutive(int[] nums){
Set<Integer> set = new HashSet<>();
for (int num : nums)
set.add(num);// 元素儲存到集合set中
int maxLen = 0;
for (int num : nums) {
if (!set.contains(num - 1)) {// 判斷是否是起始位置
int curNum = num;
// 從起始位置開始尋找連續序列的長度
int len = 1;
while (set.contains(curNum + 1)) {
curNum++;
len++;
}
maxLen = Math.max(maxLen, len);
}
}
return maxLen;
}


C++：

public:
intlongestConsecutive(vector<int> &nums){
unordered_set<int> mySet;
for (constint &num: nums)
mySet.insert(num);// 元素儲存到集合set中
int maxLen = 0;
for (constint &num: mySet) {
if (!mySet.count(num - 1)) {// 判斷是否是起始位置
int curNum = num + 1;
int len = 1;
// 從起始位置開始尋找連續序列的長度
while (mySet.count(curNum)) {
curNum++;
len++;
}
maxLen = max(maxLen, len);
}
}
return maxLen;
}


Python：

deflongestConsecutive(self, nums: List[int]) -> int:
mySet = set(nums)
maxLen = 0
for num in nums:
if num - 1notin mySet: # 判斷是否是起始位置
curNum = num # 從起始位置開始尋找連續序列的長度
len = 1
while curNum + 1in mySet:
curNum += 1
len += 1
maxLen = max(maxLen, len)
return maxLen