Two Sum
Étant donné un tableau d'entiers nums et un entier target, renvoyez les indices i et j tels que nums[i] + nums[j] == target et i != j.
LEETCODE
Antoine Latgrand NDIAYE
12/29/20242 min read
Description
[EN]
Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j. You may assume that every input has exactly one pair of indices i and j that satisfy the condition. Return the answer with the smaller index first.
[FR]
Étant donné un tableau d'entiers nums et un entier target, renvoyez les indices i et j tels que nums[i] + nums[j] == target et i != j.Vous pouvez supposer que chaque entrée a exactement une paire d'indices i et j qui satisfait la condition. Renvoyez la réponse avec l'indice le plus petit en premier.
Approche initiale : Double boucle imbriquée
Ma première approche consiste à utiliser une double boucle, en comparant la somme des valeurs aux deux indices à la cible. Dès qu'on tombe sur une valeur égale à la cible (étant donné qu'il en existe une unique), on renvoie le résultat.
Complexité temporelle : O(n²)
Complexité spatiale : O(1).
Cette approche a une complexité temporelle quadratique, ce qui devient problématique lorsque le tableau devient grand
Approche optimisée: Utilisation d'une HashMap
La première méthode ayant une complexité temporelle trop élevée, j'ai du revoir mon approche et utiliser une HashMap pour obtenir des résultats plus satisfaisants
Initialisation :
Une HashMap est créée. Cette dernière prend pour clés la différence d'un entier du tableau avec la cible, et pour valeur l'indice où se trouve cet entier
Parcours du tableau :
On parcourt chaque élément nums[i] du tableau.
Ajout au HashSet :
On calcule differenceWithTarget qui représente la différence entre la cible et la valeur actuelle
On vérifie ensuite si la valeur que l'on vient de calculer est présente comme clé dans notre map, et le cas échéant, on renvoie l'indice associé dans la map, ainsi que l'indice actuel.
On ajoute la différence actuelle calculée ainsi que son indice dans la map
Complexité temporelle :La complexité globale est O(n) du au parcours du tableau nums .
Complexité spatiale :La complexité spatiale est O(n) étant donné qu'on fait appel à une HashMap.