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