題目描述：無序的整型數組，求連續最長序列。

輸入：nums = [100,4,200,1,3,2]

輸出：4? ?（因為：最長數字連續序列是 [1, 2, 3, 4]，長度為 4。）

說明：連續指的是數字的連續，算法要求時間復雜度為O(n)。

---

求解思路：遍歷數組，依次往下找。在找的過程中，因為求最長，所以找的時候需要確定當前數是序列最小，否則沒必要。用Set容器存儲所有數作為輔助，方便確定我們找的連續序列中的數是否存在。（因為求解的最長序列，不要求在數組連續，所以想到用set去重也不會影響結果。）

class Solution {public int longestConsecutive(int[] nums) {int longest = 0;// 把所有數存在set中，方便查找HashSet<Integer> set = new HashSet<>();for (int num : nums) {set.add(num);}// 遍歷，尋找最長連續序列for (int i = 0; i < nums.length; i++) {int curNum = nums[i];//判斷前驅存不存在很重要！確保序列是從最小的curNum開始if (!set.contains(curNum - 1)) {// curNum是序列的開頭，len為1int len = 1;// 尋找curNum的下個數。前置++，++curNum和curNum+1效果一樣，但是++或者--一般用在遍歷，curNum+1更方便理解while (set.contains(curNum + 1)) {len += 1;curNum += 1;}longest = Math.max(longest, len);}}return longest;}
}

以上代碼，會報超時。

再次優化，遍歷set代替遍歷nums。

class Solution {public int longestConsecutive(int[] nums) {int longest = 0;// 把所有數存在set中，方便查找HashSet<Integer> set = new HashSet<>();for (int num : nums) {set.add(num);}// 遍歷set，因為set中比原數組數少，不存在重復的for (Integer num : set) {// 之所以這里需要使用curNum把num記錄下來，因為num是for循環進行的條件。和for(i...len)不同int curNum = num;if (!set.contains(curNum - 1)) {int len = 1;while (set.contains(curNum + 1)) {len += 1;curNum += 1;}longest = Math.max(longest, len);}}return longest;}
}

總結：判斷cur-1是核心，確保序列開頭最小。遍歷set是其二，省去重復的計算。

聯系地址：128. 最長連續序列 - 力扣（LeetCode）