2023/10/4 LeetCode

LeetCode P128最长连续序列

描述：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

解题思路：因为时间复杂度为O(n)，所以不能够先排序在进行for遍历，所以考虑使用Hash集合，因为查询的时间复杂度为O(1)，我们直接利用HashSet进行去重，外层循环需要 O(n) 的时间复杂度，同时为了防止不必要的遍历，只有当一个数是连续序列的第一个数的情况下才会进入内层循环，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。根据上述分析可知，总时间复杂度为 O(n)。

详细代码如下：

 /**
     * P128最长连续序列
     * @param nums
     * @return
     */
    public int longestConsecutive(int[] nums) {
        //去重
        HashSet<Integer> hashSet = new HashSet<>();
        for (int num : nums) {
            hashSet.add(num);
        }
        int result = 0;
        for (Integer num : hashSet) {
            if (!hashSet.contains(num-1))
            {
                int max = 1;
                int currentNum = num;
                while (hashSet.contains(currentNum+1))
                {
                    max++;
                    currentNum++;
                }
                result = Math.max(result,max);
            }
        }
        return result;
    }