法算day3

最长序列

问题描述

给定一个未排序的整数数组 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

示例 3：
输入：nums = [1,0,1,2]
输出：3

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

tip

特性 HashSet HashMap<Integer, Integer>
本质 只存“值”的集合 存“键值对”的映射表
泛型参数 （元素类型） <K, V>（键类型，值类型）
能否重复 元素不能重复 键不能重复，值可以重复
查询方式 contains(value) 判断值是否存在 get(key) 用键取值
常用方法 add(e)、remove(e)、contains(e) put(k,v)、get(k)、remove(k)

java版

方法一：先把所有数字放进“快速查找表”HashSet，然后只从每个“序列开头”往后数，数完更新最长值，保证每个数字最多被看两遍，时间复杂度就是 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int longestConsecutive(int[] nums) {
        // 如果数组是空的，直接返回 0，啥也不用干
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // 1. 先把所有数字“丢进”一个 HashSet，相当于建立一个“快速查找表”
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int maxLength = 0;   // 用来记录全局最长连续序列的长度

        // 2. 开始遍历数组
        for (int num : nums) {
            // 2.1 只有当“num-1”不在集合里时，num 才是一个连续序列的“开头”
            if (!numSet.contains(num - 1)) {
                int currentNum = num;    // 从当前这个“开头”出发
                int currentLength = 1;   // 目前这个序列长度先算 1（只有自己）

                // 2.2 不断看“下一个数字”在不在集合里，如果在就继续往后数
                while (numSet.contains(currentNum + 1)) {
                    currentNum++;      // 挪到下一个数字
                    currentLength++;   // 序列长度 +1
                }

                // 2.3 这一整条序列数完了，更新全局最大值
                maxLength = Math.max(maxLength, currentLength);
            }
        }

        // 3. 最后把最长长度返回即可
        return maxLength;
    }
}

✅ 说明：

  1. 时间复杂度
    建集合：for num in nums 一次遍历，O(n)。
    再遍历数组：看似两层循环，但每个数字最多被“往后数”一次；
    一旦某个数字被当作序列内部元素（非起点）时，根本不会进入内层 while。
    所以总工作量 ≤ 2n，仍属 O(n)。
  2. 空间复杂度
    额外开了一个集合 num_set，最坏存下所有元素，大小 n，因此 O(n)。
    总结：
    算法只多占一份“哈希表”内存，却换来线性时间，是典型“空间换时间”的套路。

python版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from typing import List

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # 1. 空数组直接返回 0
        if not nums:
            return 0

        # 2. 把所有数字放进集合，方便 O(1) 查找
        num_set = set(nums)

        max_length = 0  # 全局最长连续序列长度

        # 3. 遍历每个数字
        for num in nums:
            # 3.1 只有当 num-1 不在集合里时，num 才是一个序列的“开头”
            if num - 1 not in num_set:
                current_num = num      # 从当前数字开始往后数
                current_length = 1     # 目前序列长度至少为 1（自己）

                # 3.2 不断看“下一个数字”是否存在
                while current_num + 1 in num_set:
                    current_num += 1   # 挪到下一个数字
                    current_length += 1  # 长度 +1

                # 3.3 更新全局最大值
                max_length = max(max_length, current_length)

        # 4. 返回最长长度
        return max_length


# 简单测试
if __name__ == "__main__":
    print(Solution().longestConsecutive([100, 4, 200, 1, 3, 2]))  # 输出 4
    print(Solution().longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))  # 输出 9