LeetCode 128. 最長(zhǎng)連續(xù)序列

題目描述

給定一個(gè)未排序的整數(shù)數(shù)組 nums ，找出數(shù)字連續(xù)的最長(zhǎng)序列（不要求序列元素在原數(shù)組中連續(xù)）的長(zhǎng)度。
請(qǐng)你設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(n) 的算法解決此問(wèn)題。
示例：
輸入：nums = [100,4,200,1,3,2]
輸出：4
解釋：最長(zhǎng)數(shù)字連續(xù)序列是 [1, 2, 3, 4]。它的長(zhǎng)度為 4。

思路

1. 用一個(gè)Set將輸入數(shù)組里的元素全部存起來(lái)
2. 遍歷這個(gè)Set的Iterator，如果!set.contains(i-1)，就開(kāi)始計(jì)算序列長(zhǎng)度（之所以要做這個(gè)判斷，是因?yàn)槿绻?code>set.contains(i-1)的話，可以避免重復(fù)計(jì)算）
3. 計(jì)算序列長(zhǎng)度的方法是使用while循環(huán)，條件為set.contains(i+1)，則當(dāng)前序列長(zhǎng)度++，i++，直到set中不再包含連續(xù)的數(shù)字時(shí)結(jié)束。最后比較這次計(jì)算的序列長(zhǎng)度和最長(zhǎng)序列長(zhǎng)度，得到最終結(jié)果：max=Math.max(cur_count, max);

代碼

class Solution {public int longestConsecutive(int[] nums) {Set<Integer> set = new HashSet<>();for (int num : nums) {set.add(num);}int max = 0;Iterator<Integer> iterator = set.iterator();while (iterator.hasNext()) {int i = iterator.next();if (!set.contains(i-1)){int cur_count = 1;while (set.contains(i+1)){cur_count++;i++;}max = Math.max(cur_count, max);}}return max;}
}