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;}}