128. 最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？

解析

我们使用哈希表，然后以当前值val为起点，检查val+1,val+2,val+3...是否在set中，这里我们的时间复杂度是两层for循环，但是如果我们已知val-1在set中，那我们就不用计算val了，因为val-1一定会继续val+1,val+2...的过程，这时候我们就相当于只遍历了一遍。

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;
    }
}

注意：本文归作者所有，未经作者允许，不得转载