目录
一、哈希表理论基础
二、两种思路
2.1 使用TreeSet
2.2 使用HashSet
三、相关题目
四、总结
一、哈希表理论基础
代码随想录刷题day15|（哈希表篇）242.有效的字母异位词、383.赎金信-CSDN博客
二、两种思路
2.1 使用TreeSet
1. 去重与排序：将数组中的元素添加到TreeSet中，利用其自动去重和排序的特性。
2.寻找连续序列：遍历排序后的TreeSet，检查当前数字是否与前一个数字连续（即current == pre +1）。如果是，当前连续序列长度加1；否则，重置当前序列长度为1。
3. 更新最长序列：在遍历过程中，始终保持记录最长连续序列长度。
注意：
①如果更新最长序列长度放在else中，那么当数组是一个连续序列时，longLen最后不会被更新到，因为不会进入到else中；
②longLen初始如果为0，那么最后返回的时候要返回两者之间的较大值，如果初始为1，那么最后直接返回longLen即可，这是应对只有一个元素的情况；
时间复杂度 O(n log n)，因为TreeSet的插入和排序操作需要 O(n log n) 时间，遍历需要 O(n) 时间。
2.2 使用HashSet
1. 去重与快速查找：将所有数字存入HashSet，利用其O(1) 的查找特性，避免重复处理相同数字。
2. 寻找连续序列的起点：对于一个数字num，如果HashSet中不存在num - 1，则 num 是一个连续序列的起点。
3. 扩展连续序列：从起点num开始，依次检查num+1、num+2 是否在HashSet中，直到序列断开，记录当前序列长度。
4. 更新最长序列：在每次找到一个完整序列后，更新全局最长连续序列长度。
关键点
-
避免重复处理：通过检查num - 1是否存在，确保每个序列只被起点处理一次。
-
无需排序：直接利用数字的连续性和 HashSet的快速查找，省去 O(n log n) 的排序步骤。
为什么可以不用排序？
- 连续序列的判定仅需满足 num+1存在，与数字的具体顺序无关，无需显式排序。
- HashSet的 contains 操作是 O(1)，可以快速判断num+1是否存在，无需预先排序。
三、相关题目
128.最长连续序列
使用HashSet:
class Solution {//HashSet public int longestConsecutive(int[] nums) {if(nums.length == 0) return 0;HashSet<Integer> set = new HashSet<>();for(int num : nums){set.add(num);}int longLen = 1;for(int num : set){if(!set.contains(num -1)){int currNum = num;int currLen = 1;while(set.contains(currNum + 1)){currLen++;currNum++;}longLen = Math.max(longLen, currLen);}}return longLen;}
}使用TreeSet：
class Solution {//排序：TreeSet public int longestConsecutive(int[] nums) {//排序：TreeSet TreeSet<Integer> set = new TreeSet<>();if(nums.length == 0) return 0;for(int i = 0;i < nums.length;i++){set.add(nums[i]);}int currLen = 1;int longLen = 0;int pre = set.first();for(int num : set){if(num == pre){continue;} if(num == pre + 1){currLen = currLen + 1;longLen = Math.max(longLen, currLen);}else{//longLen = Math.max(longLen, currLen);currLen = 1;}pre = num;//1 2 4 5 6}return Math.max(longLen, currLen);}
}四、总结
使用HashSet的原理，为什么不用排序；
