最長連續(xù)序列
題目描述：給定一個未排序的整數(shù)數(shù)組 nums ，找出數(shù)字連續(xù)的最長序列（不要求序列元素在原數(shù)組中連續(xù)）的長度和泌。
請你設(shè)計并實現(xiàn)時間復(fù)雜度為 O(n) 的算法解決此問題官撼。
示例說明請見LeetCode官網(wǎng)。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-consecutive-sequence/
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)褪贵，非商業(yè)轉(zhuǎn)載請注明出處。
解法一：哈希表
因為哈希查找比較快抗俄，所以用哈希表來輔助計算竭鞍，具體處理過程如下：
- 首先板惑，用HashSet將原數(shù)組中的數(shù)字去重得到numsSet；
- 然后偎快，遍歷numsSet中的所有數(shù)字冯乘，用currentConsecutiveNums記錄以當(dāng)前數(shù)字為起點，連續(xù)的數(shù)且在numsSet中的最長序列長度晒夹，通過哈希查找在numsSet中查找這些連續(xù)的數(shù)字裆馒，最后得到當(dāng)前數(shù)字對應(yīng)的最長連續(xù)序列長度；
- 如果當(dāng)前數(shù)字對應(yīng)的最長連續(xù)序列長度比已知的最長連續(xù)序列l(wèi)ongestConsecutiveNums大丐怯，則更新最長連續(xù)序列l(wèi)ongestConsecutiveNums的值喷好。
最后，返回longestConsecutiveNums即為連續(xù)的最長序列的長度读跷。
import java.util.HashSet;
import java.util.Set;
public class LeetCode_128 {
/**
* 哈希表
*
* @param nums
* @return
*/
public static int longestConsecutive(int[] nums) {
// 去重后的數(shù)
Set<Integer> numsSet = new HashSet<>();
for (int num : nums) {
numsSet.add(num);
}
// 記錄最長的連續(xù)序列
int longestConsecutiveNums = 0;
for (Integer num : numsSet) {
if (!numsSet.contains(num - 1)) {
// 當(dāng)前的數(shù)
int currentNum = num;
// 當(dāng)前的數(shù)連續(xù)的序列的長度梗搅，初始值為1
int currentConsecutiveNums = 1;
// 獲取以當(dāng)前數(shù)字為起點，連續(xù)的數(shù)且在numsSet中的長度
while (numsSet.contains(currentNum + 1)) {
currentNum += 1;
currentConsecutiveNums += 1;
}
// 如果當(dāng)前的最大連續(xù)長度大于最大的的連續(xù)序列效览，則更新最大的連續(xù)序列
longestConsecutiveNums = Math.max(longestConsecutiveNums, currentConsecutiveNums);
}
}
return longestConsecutiveNums;
}
public static void main(String[] args) {
int[] nums = new int[]{100, 4, 200, 1, 3, 2};
// 測試用例无切，期望輸出： 4
System.out.println(longestConsecutive(nums));
}
}
【每日寄語】 第一個青春是上帝給的；第二個的青春是靠自己努力的丐枉。
