算法：最长连续序列

发布日期: 2020-06-09

题目：最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

1
2
3

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

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

分析

找到一组数的集合，我们想一下可能有的方法，动态规划？貌似没有状态转移方程可以写；滑动窗口？他不是连续的子数组。

首先依然是暴力：遍历每个数，找到每个数的时候，再遍历数组看看有没有下个数，然后再遍历，再看看有没有下个数，三次循环就可以得到以每个数为起点的最长字段。ok我们发现，复杂度是O(n^3)。这是不可接受的。然后我们来进行优化。

我们在查找每个数的下继，例如得到2 ，那我们就要看看有没有3。这种情况能不能进行优化？答案是可以的，用哈希表。我们把每个数当成key值放进哈希表，然后只要直接查询该数是否存在即可。哈希表的查询复杂度是O(1)所以这里就降低成为了O(n^2)。显然还不够，我们继续优化。

我们会发现，如果存在2,3,4,5这个集合，那么我们会轮流都去以2,3,4,5为最小值去寻找最长字符串。例如一个数组是[2,3,4,5]。第一次在下标0得到2，然后继续寻找直到得到2,3,4,5.然后第二次来到下标1得到3，我们会继续去寻找得到3,4,5，但其实，我们前面的2,3,4,5已经包含了他，所以我们不用再去寻找一遍了。所以问题来到，我们如何去记录已经得到的遍历结果？显然记录的话会有额外的空间成本，这是必然的，否则就是进行状态转换，但是显然不太行（或者你有思路可以留言分享一下）。我们会发现3,4,5之所以不行是因为前面还有一个2对不对？那么我们在遍历的时候，只需要找还有没有前继，如果没有就进行寻找最长字符串，如果有，就跳过。这样下来每个字符在形成最长连续序列中只会遍历一次，所以也就压缩了时间复杂度成为O（n）

代码实现

public int longestConsecutive(int[] nums) {
     Set<Integer> num_set = new HashSet<Integer>();
     for (int num : nums) {
         num_set.add(num);
     }

     int longestStreak = 0;

     for (int num : num_set) {
         if (!num_set.contains(num - 1)) {
             int currentNum = num;
             int currentStreak = 1;

             while (num_set.contains(currentNum + 1)) {
                 currentNum += 1;
                 currentStreak += 1;
             }

             longestStreak = Math.max(longestStreak, currentStreak);
         }
     }

     return longestStreak;
 }