[B] [C] [D]

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).

Please design and implement the time complexity of O(n) ** algorithm to solve this problem.

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

Tip:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

sort

Their thinking

In this case, the input is an unsorted array, but the subsequence is sequential, so the most direct way to think of is to sort in ascending order, and then obtain the length of the subsequence according to the nature of sequential number, and finally the maximum length of all the subsequence is the required result value.

Code implementation

Var longestavg = function(nums) {sort the input array in ascending order nums.sort((a,b) => a-b) Let Max = 0,len = 0,pre = Infinity; // iterate over the sorted input array for(let I = 0; i<nums.length; If (pre === nums[I]) continue; if(pre === nums[I]) continue; If (pre === nums[I]-1) len++ // if(pre === nums[I]-1) len++ Else Max = math.max (Max,len),len = 1 // Update pre to the current element value pre = nums[I]} // Return Max and the maximum length of the last subsequence return Math.max(max,len) };Copy the code

This solution can solve the problem, but because the sorting is done first, it does not meet the time complexity O(n) requirement in this problem.

Set

Their thinking

The input array is converted to a Set, and the Set is iterated over. If no element in the Set is found with the current element value -1, the current element is the first element in its subsequence. Initialize the current subsequence with length 1, then look for elements with the current element value +1, if found, length +1, and continue looking. When the element that meets the requirement cannot be found, it indicates that the current subsequence ends and attempts to update the result value with the current subsequence length. When iterating through the entire set, we get the length of the oldest sequence.

Code implementation:

Var longestavg = function(nums) {const set = new set (nums); // let res = 0; ForEach (item => {// If set has no current value -1, the current value is the start of its subsequence if(! Set. has(item-1)){// initialize len = 1 and let len = 1; // Subsequence length +1 when the current value +1 can be found, While (set.has(item+1)){len++,item++} res = math.max (res,len)}}) return res; };Copy the code

At this point we are done with Leetcode -128- longest continuous sequence

If you have any questions or suggestions, please leave a comment!