3.最长连续序列

raylan.chen大约 1 分钟

class Solution {
    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;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-consecutive-sequence/solutions/276931/zui-chang-lian-xu-xu-lie-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

个人理解：

对于[100, 4, 200, 1, 3, 2]来说，

如果采用哈希表存储全部元素后，使用暴力解法去解题时：

当从头遍历到 1 时，需要判断数组中是否包含 2，如果有，则需要判断是否包含 3，如果有，需要判断是否包含 4，如果有，需要判断是否包含 5；

接下来，遍历到 3 时，需要判断数组是否包含 4，如果有需要判断是否包含 5；

接下来，遍历到 2 时，需要判断数组是否包含 3，...

可以发现暴力解法中存在部分重复且没必要的工作，例如已经发现存在 1 ~ 4 的最长连续序列时，又重新判断是否包含：

3 ~ n（注意，这时数组中存在比 3 小的数）

2 ~ n（注意，这时数组中存在比 2 小的数）

的最长连续序列，

所以可以加上 if (!num_set.contains(num - 1)) { 来去掉不必要的遍历过程

3.最长连续序列

3.最长连续序列

参考链接

优秀题解