leetcode 128. 最长连续序列

2023.10.23

        本题思路：遍历所有元素，对当前元素num进行查找：有无元素(num+1)、有无元素(num+2)......若有则继续查找下去，同时记录最大序列长度，无则遍历下一个元素。

        考虑到数组中可能有重复元素需要去重，并且有查找操作，可以使用HashSet集合，既可以去除重复元素，又方便进行查找操作。

        这里可以进行一个优化：对于每一个当前元素可以进行一个判断：对hash表进行查找，如果当前这个元素有前驱元素(如：3的前驱是2，2的前驱是1),则跳过这个元素进行下一轮遍历，因为当前元素有前驱的话，你求出来的序列长度不可能是最长的，这样可以节省很多时间复杂度。

         具体java代码如下：

class Solution {public int longestConsecutive(int[] nums) {Set<Integer> hashSet = new HashSet<>();int ans = 0;for(int num : nums){hashSet.add(num);}for(int num : hashSet){if(!hashSet.contains(num-1)){ //不进行此判断会多出很多无意义的循环int local_ans = 1; //局部最长序列while(hashSet.contains(num+1)){local_ans++;num++;}ans = Math.max(ans,local_ans);//更新全局最长序列}}return ans;}
}