LeetCode_哈希表_中等_128.最长连续序列

ゞ浴缸里的玫瑰 2023-10-06 22:43 57阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

**请你设计并实现时间复杂度为 O(n) 的算法解决此问题。**

**示例 1：**  
输入：nums = \[100,4,200,1,3,2\]  
输出：4  
解释：最长数字连续序列是 \[1, 2, 3, 4\]。它的长度为 4。

**示例 2：**  
输入：nums = \[0,3,7,2,5,8,4,6,0,1\]  
输出：9

**提示：**  
0 <= nums.length <= 105  
\-109 <= nums\[i\] <= 109

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/longest-consecutive-sequence

## 2.思路 ##

**注：字节二面原题**

（1）排序(但不符合题目要求)

*  对输入的整型数组进行升序排序。
 *  遍历数组中的每个数字，查找连续的序列。
 *  使用一个变量记录当前序列的长度，以及另一个变量记录最长的序列长度。
    
     *  如果遇到相邻的数字相差为 1，则增加当前序列的长度。
     *  如果遇到相邻的数字相等，则跳过这些相等的数字。
     *  如果遇到相邻的数字不相邻，则说明当前序列结束，将当前序列长度与最长序列长度进行比较，更新最长序列长度。
 *  最后返回最长的连续序列长度。

（2）哈希集合  
思路参考[本题官方题解][Link 1]。

主要思路为：通过将数组中的元素存放到 HashSet 中，去除了重复元素，并且遍历 HashSet 中的元素，**以每个元素为起点去查找连续的元素，更新最大的连续序列长度。**

## 3.代码实现（Java） ##

//思路1————排序(但不符合题目要求)
    class Solution {
        
        public int longestConsecutive(int[] nums) {
        
            //对数组元素进行升序排序
            Arrays.sort(nums);
            int length = nums.length;
            if (length <= 1)  {
        
                return length;
            }
            int maxLength = 1;
            for (int i = 1; i < length; i++) {
        
                int tmpLength = 1;
                //遍历每个数字连续的序列，用 res 记录最长的结果
                while (i < length) {
        
                    if (nums[i] == nums[i - 1] + 1) {
        
                        tmpLength++;
                        i++;
                    } else if (nums[i] == nums[i - 1]) {
        
                        //跳过排序后相同元素相邻的情况
                        i++;
                    } else {
        
                        break;
                    }          
                }
                maxLength = Math.max(maxLength, tmpLength);
            }
            return maxLength;
        }
    }

//思路2————哈希集合
    class Solution {
        
        public int longestConsecutive(int[] nums) {
        
            //将数组中的元素存放到 hashSet 中，以去除重复元素
            Set<Integer> hashSet = new HashSet<>();
            for (int num : nums) {
        
                hashSet.add(num);
            }
            int maxLength = 0;
            for (int num : hashSet) {
        
                if (!hashSet.contains(num - 1)) {
        
                    int curNum = num;
                    int tmpLength = 1;
                    while (hashSet.contains(++curNum)) {
        
                        tmpLength++;
                    }
                    maxLength = Math.max(maxLength, tmpLength);
                }
            }
            return maxLength;
        }
    }

[Link 1]: https://leetcode.cn/problems/longest-consecutive-sequence/solution/zui-chang-lian-xu-xu-lie-by-leetcode-solution/