Leetcode deux somme
J'apprends actuellement le c ++ à partir d'un arrière-plan python, je vais donc inclure une solution en python et en c ++ pour l'énoncé de problème suivant:
Étant donné un tableau de nombres entiers et une cible entière, retourne les indices des deux nombres tels qu'ils s'additionnent à la cible. Vous pouvez supposer que chaque entrée aurait exactement une solution, et vous ne pouvez pas utiliser le même élément deux fois. Vous pouvez renvoyer la réponse dans n'importe quel ordre.
Exemple 1:
Entrée: nums = [2,7,11,15], target = 9
Sortie: [0,1]
Exemple 2:
Entrée: nums = [3,2,4], target = 6
Sortie: [1,2]
J'aimerais entendre vos commentaires / suggestions d'amélioration des performances / autres suggestions. Voici le lien
two_sum.py
def two_sum(nums: list, target: int):
for i, n in enumerate(nums):
match = target - n
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
if __name__ == '__main__':
if result := two_sum([2, 7, 11, 15], 22):
print(f'Indices:\n{result}')
else:
print('No matches found')
Statistiques Leetcode:
Durée d'exécution: 772 ms, plus rapide que 36,98% des soumissions en ligne Python pour Two Sum. Utilisation de la mémoire: 14,4 Mo, moins de 49,82% des soumissions en ligne Python pour Two Sum.
two_sum.h
#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H
#include <iostream>
#include <vector>
using std::vector;
using std::cout;
using std::endl;
vector<int> two_sum_solution(vector<int> &nums, int target) {
vector <int> results;
for (int i = 0; i < nums.size(); ++i) {
int match = target - nums[i];
for (int j = i + 1; j < nums.size(); ++j) {
if (nums[j] == match) {
for (int index_match : {
i, j
})
results.push_back(index_match);
}
}
}
return results;
}
#endif //LEETCODE_TWO_SUM_H
main.cpp
#include <vector>
#include "two_sum.h"
using std::vector;
int main() {
vector<int> v1{2, 7, 11, 15};
vector<int> v = two_sum_solution(v1, 22);
if (!v.empty()) {
cout << "Indices:" << endl;
for (auto i: v)
cout << i << " ";
}
else (cout << "No matches found");
}
Statistiques Leetcode:
Durée d'exécution: 384 ms, plus rapide que 34,03% des soumissions en ligne C ++ pour Two Sum. Utilisation de la mémoire: 9,3 Mo, moins de 12,99% des soumissions en ligne C ++ pour Two Sum.
Réponses
Je ne suis pas un expert en C ++ mais je peux donner un retour sur la solution Python.
Votre solution actuelle s'exécute dans \$O(n^2)\$. En gros, pour chaque numéro nde l'entrée nums, recherchez target - ndans nums. Comment l'améliorer?
La deuxième partie de l'algorithme peut être améliorée à partir de \$O(n)\$à \$O(1)\$. Au lieu de chercher target - ndans une liste, vous pouvez utiliser un dictionnaire:
def two_sum(nums: list, target: int):
num_index = {}
for i, n in enumerate(nums):
match = target - n
if match in num_index:
return num_index[match], i
num_index[n] = i
return -1
Résultats:
Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB
N'incluez que les fichiers d'en-tête dont vous avez besoin
Dans votre two_sum.hfichier, vous n'en avez pas besoin iostream, car vous n'utilisez aucune de ses fonctionnalités. N'oubliez pas que #includecopiez-colle littéralement le fichier, donc si vous incluez ce fichier d'en-tête dans plusieurs fichiers, cela pourrait potentiellement ralentir vos temps de compilation.
Déclarations et définitions fractionnées
En règle générale, vous divisez vos fichiers en deux parties: le fichier d'en-tête (se terminant normalement par *.h, *.hpp, *.hh) et le fichier source (se terminant normalement par *.cpp, *.cc). Le fichier d'en-tête ne comprend que les déclarations et le fichier source contient l'implémentation.
Donc, dans votre cas, votre fichier d'en-tête ressemblera à ceci:
two_sum.h
#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H
#include <vector>
std::vector<int> two_sum_solution(std::vector<int> &nums, int target);
#endif // LEETCODE_TWO_SUM_H
et votre fichier source ressemblera à ceci:
two_sum.cpp
#include "two_sum.h"
std::vector<int> two_sum_solution(std::vector<int> &nums, int target)
{
...
}
En fait, si vous essayez d'inclure votre two_sum.h(avec l'implémentation) dans plusieurs fichiers, vous enfreindriez la règle à définition unique . Vos fichiers source contiendraient plusieurs définitions de la même fonction, et l'éditeur de liens crachera une erreur. Une façon de se déplacer est de marquer les fonctions inline, mais vous voudrez probablement faire la première.
Non using namespacedans les fichiers d'en-tête
Ne faites pas using namespaceou l'une de ses variantes dans un fichier d'en-tête. Étant donné que le fichier d'en-tête est copié dans plusieurs fichiers source, il peut provoquer des erreurs gênantes. Vois ici
Utiliser la référence const
Puisque two_sum_solutionne modifie pas le numsvecteur, passez-le par référence const.
size_t vs int pour les indices de tableau
Envisagez d'utiliser size_t au lieu de int pour les indices de tableau
Utilisez autoautant que possible
Il existe quelques instances dans votre code que vous pouvez utiliser autoau lieu de spécifier le type. Exemples:
auto match = target - nums[i]; auto v = two_sum_solution(v1, 22);
La boucle la plus intérieure est inutile
Faites simplement
results.push_back(i);
results.push_back(j);
De plus, une fois que vous avez trouvé la solution, vous souhaiterez peut-être renvoyer le résultat immédiatement.
Vous pouvez peut-être améliorer les performances en créant une carte de valeur -> index dans la première itération sur le tableau donné.
Actuellement, votre programme effectue les opérations suivantes (complexité temporelle):
- itérer sur toutes les
index, valuepaires du tableau ( \$ O(n) \$) - rechercher
target - valuedans le tableau ( \$ O(n) \$) - index de recherche de
target - value( \$ O(n) \$)
Et comme ils sont tous imbriqués, vous arrivez à \$ O(n^2) \$(ce n'est pas \$ n^3 \$ car la dernière recherche n'est pas effectuée pour chaque itération).
Ma solution proposée:
- Créez une carte / dict de
{value: index}( \$ O(n) \$) - Itérer sur le
index, valuetableau ( \$ O(n) \$) - Rechercher et renvoyer l'index à partir de la carte / dict ( \$ O(1) \$)
def two_sum(numbers: list[int], target: int):
lookup: dict = {
value: index
for index, value in enumerate(numbers)
}
for index, value in enumerate(numbers):
match = target - value
if search_index := lookup.get(match):
return index, search_index
return None
Cela m'intéresse parce que je viens d'un milieu C et que j'ai commencé à utiliser Python ces dernières années pour mon travail, j'ai donc eu le chemin inverse comme vous. Quand j'ai commencé Python, j'ai grandement préféré des solutions comme la vôtre parce que parcourir les listes est tellement explicite et clair.
Cependant, j'ai appris depuis que les programmeurs Python plus compétents au travail comprennent mieux mon code lorsque j'utilise la bibliothèque standard. Une fois que j'ai commencé à investir dans l'apprentissage de ces outils, cela a eu le double effet de 1) rendre mon code plus succinct et 2) être plus efficace dans le temps et / ou dans l'espace.
Dans ce cas, je résoudrais le problème avec combinationsle itertoolspackage:
from itertools import combinations
def two_sum(nums, target):
pairs_with_indices = combinations(enumerate(nums), 2)
# result is a generator comprehension.
winning_pairs = ((index_i, index_j)
for (index_i, i), (index_j, j) in pairs_with_indices
if sum((i, j)) == target)
# Insert as much error checking as you need...
return next(winning_pairs)
Il existe probablement une solution encore meilleure, plus succincte et claire, utilisant Numpy, qui est effectivement une bibliothèque standard dans mon domaine de travail (science des données), mais ce n'est pas vrai partout.
Une chose qui diffère de votre code: il n'y a pas de place pour les erreurs ponctuelles. D'après mon expérience, un code comme celui-ci
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
est facile à écrire pour moi, difficile à lire et la maintenabilité couvre toute la gamme de facile à impossible. En d'autres termes, la gestion manuelle des index en Python me donne juste assez de corde pour m'accrocher, et les fonctions de bibliothèque standard ont été une excellente alternative.
Connaissez vos conteneurs
std::unordered_mapest votre ami dans ce problème. Chaque fois que vous n'avez jamais vu un nombre auparavant, utilisez simplement la fonction operator[]ou insertpour ajouter le nombre et son index. Lors de l'utilisation find, il renverra un itérateur, qui est une key-valuepaire.
par exemple: auto location = m.find(numToFind);
location->firstest votre clé et location->secondvotre valeur
À votre retour, n'utilisez pas push_back
Vous pouvez simplement retourner une liste d'initialiseur comme: {i,j}.