Longest Consecutive Sequence

Description

[EN]

Given an array of integers nums, return the length of the longest consecutive sequence of elements that can be formed.

A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. The elements do not have to be consecutive in the original array.

You must write an algorithm that runs in O(n) time.

Constraints:

• 0 <= nums.length <= 1000

• -10^9 <= nums[i] <= 10^9

[FR]

Étant donné un tableau d'entiers nums, retournez la longueur de la plus longue séquence consécutive d'éléments qui peut être formée.

Une séquence consécutive est une séquence d'éléments dans laquelle chaque élément est exactement 1 de plus que l'élément précédent. Les éléments n'ont pas besoin d'être consécutifs dans le tableau d'origine.

Vous devez écrire un algorithme qui s'exécute en O(n).

Contraintes :

• 0 <= nums.length <= 1000 : Le tableau peut contenir entre 0 et 1000 éléments.

• -10^9 <= nums[i] <= 10^9 : Chaque élément du tableau est compris entre -1 milliard et 1 milliard.

Approche : Utilisation d 'une HashMap et d'un HashSet

• On utilise un HashSet pour stocker les nombres de nums.

• Pourquoi un HashSet ?

  • Permet un accès rapide pour vérifier si un élément existe (O(1)O(1)O(1)).

  • Évite les doublons.

• On crée une HashMap où :

  • Clé : Le premier élément d'une séquence consécutive.

  • Valeur : Une ArrayList représentant la séquence.

• On parcourt chaque nombre dans le HashSet.

• Si le nombre précédent (i−1) n'existe pas dans le HashSet, cela signifie que i est le début d'une nouvelle séquence.

• Une nouvelle séquence est alors créée et ajoutée à la HashMap avec i comme clé.

• Après avoir identifié les débuts de séquences, on essaie d'étendre chaque séquence.

• On commence à i+1 et on vérifie si le nombre suivant existe dans le HashSet.

• Si c'est le cas, on ajoute ce nombre à la séquence dans la HashMap.

• On continue ce processus jusqu'à ce qu'il n'y ait plus de nombre consécutif.

• Après avoir construit toutes les séquences, on parcourt les valeurs de la HashMap et on trouve la taille de la séquence la plus longue.

• Complexité temporelle: O(n) 

• Complexité spatiale: O(n)