最长连续序列

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

解法1:排序。之后找出最长连续递增子序列。

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        Arrays.sort(nums);

        int longestStreak = 1;
        int currentStreak = 1;

        for (int i = 1; i < nums.length; i++) {//从第二个数字开始
            if (nums[i] != nums[i-1]) {
                if (nums[i] == nums[i-1]+1) {//-1，0，1，3，5
                    currentStreak += 1;
                }
                else {
                    longestStreak = Math.max(longestStreak, currentStreak);//最大3
                    currentStreak = 1;//从3开始又为1
                }
            }
        }

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

解法2:利用hHashset去掉重复数字。在不重复的数组中找出连续序列中最小的。

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)) {//9，7，4，1，0，-1
                int currentNum = num;
                int currentStreak = 1;

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

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

        return longestStreak;
    }
}