Sword finger offer II 119 Longest continuous sequence

The finger of the sword Offer II 119. The longest continuous sequence 【 Medium question 】

Ideas ：【 Union checking set 】【 Hashtable 】

A hash table alone can pass , But it takes time 253 ms
The basic idea is to store array elements in hash set, Then traverse the array elements , Let the current element traversed be num , If set in num-1, It means that this element has been num-1 I did , Just skip ; The starting element of the continuous sequence we are looking for must have never been found before .
With num As a starting point ,num+1 As the target target, Get into while loop , When the target target When it exists in the list , Record the number cnt++, Target shift right ,target++.
Update the longest continuous sequence length starting from the current element .
See code for specific implementation 1.

Use the union search set where the parent node is stored by the hash table to solve , Time consuming 53 ms
The basic idea and code implementation refer to the boss of the self review area yukiyama

Code 1：

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

Code 2：

class Solution {
    
    public int longestConsecutive(int[] nums) {
    
        if (nums.length <= 1){
    
            return nums.length;
        }
        UnionFindByHashMap uf = new UnionFindByHashMap(nums);
        // Traverse  parents Of key aggregate , Try to key+1 And key connected , namely  key -> key+1
        for (Integer key : uf.parents.keySet()) {
    
            uf.union(key,key+1);
        }
        int max = 1;
        for (Integer key : uf.parents.keySet()) {
    
            //key The root node pointed to is key The maximum value that can be reached by adding one by one , So now key The length of the longest continuous sequence starting from is  find(key)-key+1
            max = Math.max(max,uf.find(key)-key+1);
        }
        return max;
    }
}

class UnionFindByHashMap {
    

    int count;// Record the connected components 
    Map<Integer,Integer> parents;// Record nodes key The root node of is value

    /** *  Constructors , Initialize the merge process  * @param nums  To build and look up an array of sets  */
    public UnionFindByHashMap(int[] nums){
    
        this.parents = new HashMap<>();
        // Use hash map De duplication of nodes in the array 
        // In the initial state, each node is disconnected , The root node of each node is itself 
        for (int num : nums) {
    
            this.parents.put(num,num);
        }
        // Initialize the number of connected components 
        this.count = this.parents.size();
    }

    /** *  Find node  x  The root node  * @param x  Incoming node  * @return  Return the root node of the incoming node  */
    public int find(int x){
    
        // When x The root node of the node is x when , return x
        if (parents.get(x) == x){
    
            return x;
        }
        // When x The root node of the node is not x when , Recursively find this time x The root node of the root node 
        parents.put(x,find(parents.get(x)));
        // Back at this point x The root node 
        return parents.get(x);
    }

    /** *  take  x  node   and  y  Nodes are connected  * @param x  Incoming node  * @param y  Incoming node  */
    public void union(int x,int y){
    
        if (parents.containsKey(y)){
    
            // Direct will y Put it in x Of value Location , Express order  x  Point to  y
            parents.put(x,y);
            // After connection, the connected component decreases 1
            count--;
        }
    }

    /** *  Returns the current number of connected components  * @return */
    public int getCount(){
    
        return this.count;
    }
}