😮128 longest consecutive sequence

https://leetcode.com/problems/longest-consecutive-sequence/

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        int longestStreak = 0;
        for (int num: nums) {
            // 只考虑能作为起始的数
            if (!numSet.contains(num - 1)) {
                int curNum = num;
                int streak = 1;
                while (numSet.contains(curNum + 1)) {
                    streak++;
                    curNum++;
                }
                longestStreak = Math.max(longestStreak, streak);
            }
        }
        return longestStreak;
    }
}

找到每个可能是起点的数(num-1不在list里), 然后往后数到下一个数不在list里，记录长度，amortize下来时间复杂度是O(n)的

所以当条件不确定，比如一个数可以是升序起始或者降序起始时，要考虑固定一端的条件。

也可以用union find

class Solution {
    class Union {
        int[] size;
        int[] leader;
        Union(int[] nums) {
            size = new int[nums.length];
            leader = new int[nums.length];
            for (int i = 0; i < nums.length; i++) {
                leader[i] = i;
                size[i] = 1;
            }
        }
        int union(int a, int b) {
            int la = find(a);
            int lb = find(b);
            if (la == lb) {
                return size[la];
            }
            if (size[la] >= size[lb]) {
                size[la] += size[lb];
                leader[lb] = la;
                return size[la];
            } else {
                size[lb] += size[la];
                leader[la] = lb;
                return size[lb];
            }
        }
        int find(int a) {
            if (leader[a] == a) {
                return a;
            }
            leader[a] = find(leader[a]);
            return leader[a];
        }
    }
    public int longestConsecutive(int[] nums) {
        Union union = new Union(nums);
        Map<Integer, Integer> map = new HashMap();
        int len = 0;
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int num : nums) {
            if (map.containsKey(num-1)) {
                len = Math.max(len, union.union(map.get(num), map.get(num-1)));
            }
            if (map.containsKey(num+1)) {
                len = Math.max(len, union.union(map.get(num), map.get(num+1)));
            }
            len = Math.max(len, union.size[map.get(num)]);
        }
        return len;
    }
}