最长连续序列

题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

  • 示例
1
2
3
给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。
  • 示例:
1
2
3
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

解题思路

  • 围绕 O(n)O(n) 的时间复杂度
  • 这些数字用一个 HashSet 保存，实现 O(1)O(1) 时间的查询
  • 我们只对 当前数字 - 1 不在哈希表里的数字，作为连续序列的第一个数字去找对应的最长序列，这是因为其他数字一定已经出现在了某个序列里。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static int longestConsecutive() {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    Set<Integer> tempNums = new HashSet<>();
    for (int num : nums) {
        tempNums.add(num);
    }
    int result = 0;
    for (Integer item : tempNums) {
        if (!tempNums.contains(item - 1)) {
            int currentNum = item;
            int index = 1;
            while (tempNums.contains(currentNum + 1)) {
                index++;
                currentNum++;
            }
            result = Math.max(result, index);
        }
    }
    return result;
}

性能分析

一、执行用时分布图表

  • time

二、执行消耗内存分布图表

  • memory

三、复杂度分析

  • 时间复杂度：O(n)O(n)

尽管在 for 循环中嵌套了一个 while 循环，时间复杂度看起来像是二次方级别的。但其实它是线性的算法。因为只有当 currentNum 遇到了一个序列的开始， while 循环才会被执行（也就是 currentNum-1 不在数组 nums 里）， while 循环在整个运行过程中只会被迭代 nn 次。这意味着尽管看起来时间复杂度为 O(n \cdot n)O(n⋅n) ，实际这个嵌套循环只会运行 O(n + n) = O(n)O(n+n)=O(n) 次。所有的计算都是线性时间的，所以总的时间复杂度是 O(n)O(n) 的。

  • 空间复杂度：O(n)O(n)

为了实现 O(1)O(1) 的查询，我们对哈希表分配线性空间，以保存 nums 数组中的 O(n)O(n) 个数字。除此以外，所需空间与暴力解法一致。

总结

  • 如果代码中不加如果的if语句也是OK的，但是复杂度就高了很多，大家可以亲测
1
if (!tempNums.contains(item - 1)) {