class Solution {
    public int longestConsecutive(int[] nums) {
        // 以下做法是不对的，因为没有考虑到数组中从在两个相同的数这种情况，相比较还是用for循环做更合适
//         if(nums.length == 0)
//             return 0;
        
//         Arrays.sort(nums);
//         int i = 0;
//         int max = 1;
//         while(i<nums.length-1) {
//             int len = 1;
//             while(i < nums.length-1 && nums[i+1] == (nums[i]+1)) {
//                 i++;
//                 len++;
//             }
//             max = Math.max(max,len);
//             i++;
//         }
 
        // 方法一 以下做法复杂度取决于sort: O(nlogn) for循环复杂度为O(n)
//         if(nums.length == 0)
//             return 0;
        
//         Arrays.sort(nums);
//         int max = 1;
//         int curr = 1;
//         for(int i = 0;i<nums.length-1;i++) {
//             if(nums[i+1] != nums[i]) {
//                 if(nums[i+1] == (nums[i] + 1))
//                     curr++;
//                 else {
//                     max = Math.max(max,curr);
//                     curr = 1;
//                 }
//             }
//         }
//         max = Math.max(max,curr);
//         return max;
        
        // 方法二
        if(nums.length == 0)
            return 0;
        int max = 1;
        Set<Integer> set = new HashSet<Integer>();
        for(int i:nums)
            set.add(i);
        
        for(int num:set) {
            if(!set.contains(num-1)) {
                int len = 1;
                int currnum = num+1;
                while(set.contains(currnum)) {
                    len++;
                    currnum++;
                }
                max = Math.max(max, len);
            }
        }
        return max;
    }
}