Vérifiez si N et son double existent

1346. Vérifiez si N et son double existent

Difficulté :Facile

Sujets : Tableau, table de hachage, deux pointeurs, recherche binaire, tri

Étant donné un tableau arr d'entiers, vérifier s'il existe deux indices i et j tels que :

• je != j
• 0 <= je, j < arr.longueur
• arr[i] == 2 * arr[j]

Exemple 1 :

• Entrée : arr = [10,2,5,3]
• Sortie : vrai
• Explication : Pour i = 0 et j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

Exemple 2 :

• Entrée : arr = [3,1,7,11]
• Sortie : faux
• Explication : Il n'y a pas de i et de j qui satisfont aux conditions.

Contraintes :

• 2 <= longueur arr. <= 500
• -10³ <= arr[i] <= 10³

Indice :

1. Boucle de i = 0 à arr.length, en conservant dans une hashTable les éléments du tableau de [0, i - 1].
2. À chaque étape de la boucle, vérifiez si nous avons vu l'élément 2 * arr[i] jusqu'à présent.
3. Vérifiez également si nous avons vu arr[i] / 2 au cas où arr[i] % 2 == 0.

Solution :

Nous pouvons utiliser une table de hachage (tableau associatif) pour suivre les éléments que nous avons déjà rencontrés lors de l'itération dans le tableau. L'idée est de vérifier pour chaque élément arr[i] si son double (c'est-à-dire 2 * arr[i]) ou sa moitié (c'est-à-dire arr[i] / 2 si c'est un nombre pair) a déjà été rencontré.

Voici une solution étape par étape :

Plan:

1. Parcourez le tableau.
2. Pour chaque élément arr[i], vérifiez si on a vu 2 * arr[i] ou arr[i] / 2 (si arr[i] est pair) dans la table de hachage.
3. Si une condition est satisfaite, retournez vrai.
4. Sinon, ajoutez arr[i] à la table de hachage et passez à l'élément suivant.
5. Si aucune correspondance n'est trouvée à la fin, renvoie false.

Implémentons cette solution en PHP : 1346. Vérifiez si N et son double existent

  
  
  Explication:




Hash Table : Nous utilisons le tableau associatif $hashTable pour stocker les éléments que nous avons rencontrés jusqu'à présent.

Première Condition : Pour chaque élément arr[i], on vérifie si arr[i] * 2 existe dans la table de hachage.

Deuxième condition : Si l'élément est pair, on vérifie si arr[i] / 2 existe dans la table de hachage.

Ajout à la table de hachage : Après vérification, nous ajoutons arr[i] à la table de hachage pour référence future.

Retour : Si nous trouvons une correspondance, nous renvoyons immédiatement vrai. Si aucune correspondance n'est trouvée après la boucle, nous renvoyons false.



  
  
  Complexité temporelle :



La complexité temporelle est O(n), où n est la longueur du tableau. En effet, chaque élément est traité une fois et la vérification ou l'ajout d'éléments dans la table de hachage prend en moyenne un temps constant.



  
  
  Complexité spatiale :



La complexité spatiale est O(n) en raison du stockage requis pour la table de hachage.


Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!