### 题目描述 给定一个未排序的整数数组 `nums`，找出其中最长连续元素序列的长度。要求算法的时间复杂度为 O(n)，其中 n 是数组 `nums` 的长度。 **示例 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 ``` ### 解题思路 1. 使用一个哈希集合（HashSet）来存储数组中的所有元素，以便快速查找某个元素是否存在。 2. 遍历数组中的每个元素 `num`，仅当 `num - 1` 不在哈希集合中时，才开始从 `num` 出发查找连续序列。这是为了避免重复计算连续序列（即，对于数组中的每个连续序列，我们仅从最小的元素开始计算一次）。 3. 对于每个满足条件的 `num`，开始向后查找连续的数，直到某个数不在哈希集合中为止，记录下这段连续序列的长度。 4. 在遍历过程中，不断更新最长连续序列的长度。 ### PHP 代码示例 ```php function longestConsecutive($nums) { if (empty($nums)) { return 0; } $numSet = array_flip($nums); // 使用数组翻转创建哈希集合 $maxLength = 0; foreach ($nums as $num) { if (!isset($numSet[$num - 1])) { // 仅当 num-1 不在集合中时开始检查 $currentNum = $num; $currentLength = 1; while (isset($numSet[$currentNum + 1])) { // 向后查找连续序列 $currentNum++; $currentLength++; } $maxLength = max($maxLength, $currentLength); } } return $maxLength; } ``` ### Python 代码示例 ```python def longestConsecutive(nums): if not nums: return 0 num_set = set(nums) max_length = 0 for num in nums: if num - 1 not in num_set: # 仅当 num-1 不在集合中时开始检查 current_num = num current_length = 1 while current_num + 1 in num_set: # 向后查找连续序列 current_num += 1 current_length += 1 max_length = max(max_length, current_length) return max_length ``` ### JavaScript 代码示例 ```javascript function longestConsecutive(nums) { if (nums.length === 0) { return 0; } const numSet = new Set(nums); let maxLength = 0; for (let num of nums) { if (!numSet.has(num - 1)) { // 仅当 num-1 不在集合中时开始检查 let currentNum = num; let currentLength = 1; while (numSet.has(currentNum + 1)) { // 向后查找连续序列 currentNum++; currentLength++; } maxLength = Math.max(maxLength, currentLength); } } return maxLength; } ``` 在以上三种语言的实现中，我们都遵循了相同的逻辑，并且使用了哈希集合来优化查找过程，以确保算法的时间复杂度为 O(n)。