128. 最长连续序列（高频题）

128. 最长连续序列

• 解题思路
• 代码

解题思路

1. 对于数组nums，其可能有多个数字连续的序列，其中每个序列都会有一个左边界，例如示例1的结果中[1, 2, 3, 4]的左边界就为1。
2. 如果我们知道了每一个连续序列的左边界，并且知道以它为左边界的连续序列的长度。进而就可以知道所有连续序列的长度。在其中取最大值即为结果。
3. 但都有哪些数可以成为连续序列的左边界呢？
4. 设想，如果num为一个左边界，那么num - 1就不应该存在于数组中（因为如果num - 1存在于数组中，num - 1又与num连续，所以num不可能是连续序列的左边界）。
   因此如果一个数字num满足：num-1不存在于数组中。这个数字num就可以成为连续序列的左边界。
   

代码

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int res = 0;
        for (int num : nums) {
            if (set.contains(num - 1)) {
                continue;
            } else {
                //len记录以num为左边界的连续序列的长度
                int len = 0;
                while (set.contains(num++)) {
                    len++;
                }
                res = Math.max(res, len);
            }
        }
        return res;
    }
}