D3

128.最長連續序列

錯解

class Solution {public int longestConsecutive(int[] nums) {Arrays.sort(nums);int maxCnt = 0;int cnt = 0;for (int i = 0; i < nums.length - 1; i++) {if(nums[i] != nums[i + 1] - 1){//如果不連續，取cnt與maxCnt較大值，cnt清零maxCnt = Math.max(cnt, maxCnt);cnt = 0;}else{cnt++;maxCnt = Math.max(cnt, maxCnt);}}return maxCnt = maxCnt != 0 ? maxCnt + 1 : maxCnt;}
}

這里我犯了一個錯誤，把連續理解為了，索引連續并且元素大小連續。事實上，題目中只需要保證元素大小連續即可，比如1 1 2 2 3，最大連續長度為3，最先想到的是用Treeset去重排序，但我看題目提示是哈希表。

TreeSet樸素解法

就是提供兩個計數器，記錄連續元素的長度以及最大長度，雖然是一次for循環就解決了，但是TreeSet的排序時間復雜度是O(log n)，所以總體時間復雜度是O(nlogn)，是不符合題意的。

class Solution {public int longestConsecutive(int[] nums) {int cnt = 1; //當前連續長度int maxCnt = 1; //Set<Integer> set = new TreeSet<>();for (int num : nums) {set.add(num);}if(set.isEmpty()) return 0;if(set.size() == 1) return 1;Iterator<Integer> it = set.iterator();int prev = it.next();while(it.hasNext()){int current = it.next();if(current != prev + 1){maxCnt = Math.max(maxCnt, cnt);cnt = 1;}else{cnt++;maxCnt = Math.max(maxCnt, cnt);}prev = current;}return maxCnt;}
}

HashSet解法

這種方法時間復雜度為O(n)，符合題意。

思路：

使用set是為了保證元素不重復，降低時間復雜度，因為題目有說，不要求元素在原序列連續。如果集合中有元素x-1，那么最長長度一定是從x-1開始，比如數組1 2 4 6 7 8 9，如果有6，那么從6開始的序列最長長度就不會從7開始，所以只要統計出從某個元素開始的連續元素的最大值，某個元素到這個最大值的元素數目就是最大值。

代碼如下：

class Solution {public int longestConsecutive(int[] nums) {Set<Integer> set = new HashSet<>();for(int num : nums){set.add(num);}int ans = 0;for(int x : set){if(set.contains(x-1)){//如果還有更小的連續元素，找最小元素continue;}int y = x + 1;while(set.contains(y)){y++;}ans = Math.max(ans, y - x);//獲取最大元素長度}return ans;}}