3.最长连续序列

• 2.23

  • 想起来优化了，但是忘了 count 初始值为 1，包含起点本身

• 2.5

  • 忘记优化了，
    1. set 的 add天然会判断是否存在
    2. for 循环在 set 中 for
    3. 判断当前位置如果不是开头位置，则直接剪枝（通过 看num-1 存不存在）

• 1.22

  • 放入 set 后，后续在 set 里遍历，且必须剪枝（判断这个数是不是起始位置）否则时间超时

class Solution {
    public int longestConsecutive(int[] nums) {
        int max = 0;
        Set<Integer> set = new HashSet<>();
        for(int num:nums){
            set.add(num);
        }
        // for(int i=0;i<nums.length;i++){
        //     if(!set.contains(nums[i]-1)){
        //         int maxTemp =1;
        //         int ptr = i;
        //         int current = nums[ptr];
        //         while(set.contains(current+1)){
        //             maxTemp++;
        //             current++;
        //         }
        //         max = Math.max(max,maxTemp);
        //     }
        // }上面的完全超时
        for(int num:set){
            int current = num;
            int maxTemp = 1;
            if(!set.contains(num-1)){
                while(set.contains(current+1)){
                    maxTemp++;
                    current++;
                }
                max = Math.max(max,maxTemp);
            }
        }
        return max;
    }
}

• 1.5
  • 用 set 来存数组每种数字后
  • 判断当前数字有没有前面的数字来判断是否为起点 - 是起点就开始 while 遍历（结束条件是没有下一个，用 contains 实现）贪心记录最大值

第二版
class Solution {
    public int longestConsecutive(int[] nums) {
        int longest = 0;
        Set<Integer> set = new HashSet<>();
        for(int num:nums){
            set.add(num);
        }
        for(int num:set){
            if(!set.contains(num-1)){
                int length=1;
                int currentNum = num;
                while(set.contains(currentNum+1)){
                    length++;
                    currentNum++;
                }
                longest = Math.max(length,longest);
            }
        }
        return longest;
    }
}

• 把每个数放进hashset中(注意指定Integer数据类型)
• 遍历集合,找出是起点的数字(num-1不在set),尝试往后找,遍历数字

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
        }
        int longest = 0;
        for(int num:set){
            if(!set.contains(num-1)){
                int currentNum = num;
                int length = 1;
                while(set.contains(currentNum+1)){
                    currentNum++;
                    length++;
                }
            longest = Math.max(longest,length);
            }
        }
        return longest;
    }
}