Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/
给定一个int无序数组，求数组内部连续数字的最长长度
Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

本题题目要求时间复杂度是O(N)
如果排除这个条件，可以用排序O(NLogN)，然后找最长连续数字

O(N)解法

public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();

        for (int num : nums) {
            set.add(num);
        }

        int longestStreak = 0;

        for (int num : set) {

            //如果set里面有num-1，那么这个num一定不是最长序列的起始数字
            if (set.contains(num - 1)) {
                continue;
            }

            //找到起始数字
            int currentNum = num;
            int currentStreak = 1;

            while (set.contains(currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }
            longestStreak = Math.max(longestStreak, currentStreak);
        }
        return longestStreak;
    }

解法二

• 依旧是HashSet，遍历HashSet
• 发现set中有，遍历pre和next，确定连续子串的长度
• 维护一个结果集res，保证这个res是长度的最小值

public int longestConsecutive2(int[] nums) {
        int res = 0;
        Set<Integer> hashSet = new HashSet<Integer>();
        for (int num : nums) {
            hashSet.add(num);
        }

        for (int num : nums) {
            // 如果有当前num，remove
            if (hashSet.remove(num)) {
                int pre = num - 1, next = num + 1;
                while (hashSet.remove(pre)) {
                    pre--;
                }
                while (hashSet.remove(next)) {
                    next++;
                }
                res = Math.max(res, next - pre - 1);
            }
        }
        return res;
    }