最長連續(xù)序列（困難）
題目敘述：
給定一個未排序的整數(shù)數(shù)組职抡，找出最長連續(xù)序列的長度葬燎。
要求算法的時間復雜度為 O(n)。
示例：
輸入: [100, 4, 200, 1, 3, 2]
輸出: 4
解釋: 最長連續(xù)序列是 [1, 2, 3, 4]缚甩。它的長度為 4萨蚕。
解題思路：
方法一：
這個思路比較簡單，但不是我本人推薦的一個方式蹄胰，那就是將所有的元素進行一次排序，然后就從頭開始遍歷統(tǒng)計奕翔，取最大的值裕寨，這個方法如果算上排序的時間復雜度是O(nlogn)但是它反而是LeetCode上最快的方式。
代碼實現(xiàn)：
class Solution {
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) return 0;
Arrays.sort(nums);
int max = 1;
int cur = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i-1]) continue;
if (nums[i] == nums[i-1] + 1) {
cur++;
} else {
cur = 1;
}
max = Math.max(max, cur);
}
return max;
}
}
方法二：
這個思路就是按照題意的時間復雜度的來做的派继，我們將用一個Set的集合將所有的元素都存起來宾袜。大家都知道Set的查找效率是O(1)。然后我們遍歷Set將如果沒有一個比他小1的元素之后驾窟，找出以它為起始的連續(xù)的序列的長度庆猫。時間復雜度為O(n)但是LeetCode運行時間比方法一的時間要長。個人揣測出題人的意思應該是這種類似的方法吧绅络，不然不會被定為困難月培。
實現(xiàn)代碼
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> numSet = new HashSet<Integer>();
for (int num : nums) {
numSet.add(num);
}
int max = 0;
for (int num : numSet) {
if (!numSet.contains(num-1)) {
int currentNum = num;
int cnt = 1;
while (numSet.contains(currentNum+1)) {
currentNum += 1;
cnt += 1;
}
max = Math.max(max, cnt);
}
}
return max;
}
}
