Leetcode 128 longest continuous sequence (hash set)

Top1：LeetCode 128 The longest continuous sequence （ Hash set）【 There can be duplicate numbers in the array , Big that is able to use set Weight removal does not affect 】

Title Description ：
Given an array of unsorted integers nums , Find the longest sequence of consecutive numbers （ Sequence elements are not required to be contiguous in the original array ） The length of .
Please design and implement it with a time complexity of O(n) The algorithm to solve this problem .

Example 1：
Input ：nums = [100,4,200,1,3,2]
Output ：4
explain ： The longest consecutive sequence of numbers is [1, 2, 3, 4]. Its length is 4.

Example 2：
Input ：nums = [0,3,7,2,5,8,4,6,0,1]
Output ：9

One 、 Consider enumerating arrays into set after for(int num : set) Traverse , From every one x Start enumeration set Whether or not contains(x+1) Record length ; But here we have to go , That is, when traversing x There is x-1 stay set In the middle of the day , skip

Two 、 Use one current Store the traversed current num Flow length of , Again longest = Math.max(longest, current); Store the longest answer

De duplication skip details reference leetcode Slide map in the source page ： The longest continuous sequence - Hashtable

Here, save the array to set And traversal code :

Set<Integer> set = new HashSet<>();
    for (int num : nums) {
       //  duplicate removal , And the time complexity of the query is O(1)
        set.add(num);
    }
    int longest = 0;   //  Initialize the final return value , Get into for After the cycle longest = Math.max(longest, current); to update 
    for (int num : set) {
     }  //  Traverse set Hash set  // for Every one in the loop num It's all new , And the last time num No conflict , It's similar to a local variable 

You can use the complete code

public static int longestConsecutive2(int[] nums) {
    
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
       //  duplicate removal , And the time complexity of the query is O(1)
        set.add(num);
    }
    int longest = 0;   //  Initialize the final return value , Get into for After the cycle longest = Math.max(longest, current); to update 
    for (int num : set) {
       //  Traverse set Hash set  // for Every one in the loop num It's all new , And the last time num No conflict , It's similar to a local variable 
        if (!set.contains(num - 1)) {
    
// int curNum = num; //  Store the current num, Into the back of while loop 
            int current = 1;   //  to num The stream length becomes 1
            while (set.contains(num + 1)) {
    
                num += 1;
                current += 1;
            }
            longest = Math.max(longest, current);
        }
    }
    return longest;
}