This is my third article about getting started.

Topic describes

Given an unsorted integer array nums, find the length of the longest sequence in which numbers are consecutive (no sequence elements are required to be consecutive in the original array).

Advancements: Can you design and implement O(n) time complexity solutions?

Example 1:

Input: nums = [100,4,200,1,3,2] output: 4 explanation: the longest sequence of consecutive digits is [1, 2, 3, 4]. It has length 4.Copy the code

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1] output: 9Copy the code

Thought analysis

The longest sequence of numbers x is x, x+1, x+2… X +n, which has length n+1, so we can facilitate the array by finding for each number the value of n when x+n is not in the array, which is the length of the continuous sequence of x. I’m going to take the maximum length that I get each time, and that’s the length of the longest continuous sequence that WE’re looking for.

Based on the above analysis, we can find that:

  • Repeating the number x does not make sense for us to find the longest sequence in a row, so we can use the new data type Set in ES6 to deduplicate the array.
  • For the longest continuous sequence starting with any number x, there should be no x-1 in nums, so we do not need to explore the length of the continuous sequence in the case of x-1 in nums

And now let’s implement the code

Code implementation

/ * * *@param {number[]} nums
 * @return {number}* /
const longestConsecutive = nums= > {
  const numSet = new Set(nums);

  let longest = 0;

  for (const num of numSet) {
    if(! numSet.has(num -1)) {
      let n = 1;
      while (numSet.has(num + n)) {
        n++;
      }

      longest = Math.max(n, longest); }}return longest;
};
Copy the code

First we use Set to deduplicate the array. Then we define a variable to store the longest continuous sequence length, which we Set to 0 at first. Then we iterate over numSet and determine if num-1 exists in numSet for each iteration, because num-1 should not exist in numSet at the beginning of every consecutive sequence. Then, we defined variable N to represent the continuous sequence length of num. Next, we began to explore the maximum continuous sequence length of num. We compared the obtained n with the maximum recorded length and took the larger value. Returns the maximum value of the iterated array.

conclusion

Now to summarize what we did:

  1. We analyzed what is the longest continuous sequence, namely x, x+1, x+2… X plus n, length n plus 1
  2. We find that repeated numbers are meaningless for finding the longest sequence in a row
  3. For the longest continuous sequence starting with any number x, there should be no x-1 in the array NUMs
  4. We coded code to implement the algorithm