Longest continuous sequence [diffusion method + space for time]

Preface

The core of space for time is to reduce the time complexity , But sometimes it's the key to solving problems , After all, time is limited （ First, double pointer ）.
A typical space for time exchange is an array / Array hash/hash.
In this paper, we use the longest continuous sequence to experience space changing time , And practice the diffusion method .

One 、 The longest continuous sequence

Two 、 Diffusion method + Space for time

package everyday.medium;

import java.util.HashSet;
import java.util.Set;

//  The longest continuous sequence 
public class LongestConsecutive {
    
    /* target： Find the longest consecutive number inside , If you order , direct O(n) Go through it and record the longest time .  But the time complexity requires O(n), So we can only exchange space for time , First use hash Save up , It is convenient for quick search in the back ( Find by diffusion method ). */
    public int longestConsecutive(int[] nums) {
    
        //  A special case , Special treatment .
        if (0 == nums.length) return 0;
        Set<Integer> set = new HashSet<>();
        //  preparation , Record all elements , And the initial value is 1, Indicates the number of consecutive numbers 1.
        for (int n : nums) if (!set.contains(n)) set.add(n);
        //  Traverse nums, Find the total continuity of adjacent elements .
        int ans = 1;
        //  Diffusion method , Each value can be accessed up to two times , Once there was , Once none .
        for (int n : nums) {
    
            //  Unused numbers , From both sides .
            if (set.contains(n)) {
    
                //  Start spreading on both sides , Diffusion method .
                int len = 1;
                int left = n, right = n;
                while (set.contains(--left)) {
    
                    ++len;
                    set.remove(left);
                }
                while (set.contains(++right)) {
    
                    ++len;
                    set.remove(right);
                }
                //  Take the maximum length of each diffusion .
                ans = Math.max(ans, len);
            }
        }
        return ans;
    }
}

summary

1） Space for time
2） Diffusion method

reference

[1] LeetCode The longest continuous sequence