給定一個未排序的整數(shù)數(shù)組开仰，找出最長連續(xù)序列的長度。
說明
要求你的算法復(fù)雜度為O(n)
樣例
給出數(shù)組[100, 4, 200, 1, 3, 2]格了，這個最長的連續(xù)序列是 [1, 2, 3, 4]瓢湃，返回所求長度 4
思路
我們在判斷某個數(shù)的連續(xù)序列時，會分別往減小和增大的方向找下一個連續(xù)數(shù)在不在數(shù)組中系瓢。那么我們?nèi)绾闻袛辔覀円獙ふ业南乱粋€數(shù)在不在數(shù)組中呢？我們可以先建立一個HashSet句灌，先用HashSet消除數(shù)組中的重復(fù)元素(相同的兩個數(shù)只能使連續(xù)序列的長度+1)夷陋，然后查找HashSet中是否包含我們要尋找的下一個元素，包含則長度+1胰锌，繼續(xù)往下尋找骗绕，不包含則這個尋找方向就沒辦法繼續(xù)了。最后把兩個方向的長度加起來即為包含該數(shù)的一個連續(xù)序列资昧。
代碼
public class Solution {
/**
* @param nums: A list of integers
* @return an integer
*/
public int longestConsecutive(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]);
}
int longest = 0;
for (int i = 0; i < nums.length; i++) {
int down = nums[i] - 1;
while (set.contains(down)) {
// 同一序列中的所有元素酬土，不管從哪個開始進(jìn)行down和up的查找，找到的最終都是同一個序列榛搔，為了避免重復(fù)運算诺凡，要移除set中已經(jīng)查過的down和up
set.remove(down);
down--;
}
int up = nums[i] + 1;
while (set.contains(up)) {
set.remove(up);
up++;
}
// 注意上面多執(zhí)行了一次down--，所以此次要用up - (down + 1)
longest = Math.max(longest, up - down - 1);
}
return longest;
}
}
