Leetcode zwei Summe
Ich lerne derzeit C ++ aus einem Python-Hintergrund, daher werde ich eine Lösung in Python und in C ++ für die folgende Problemstellung einfügen:
Geben Sie bei einem Array von Ganzzahlnummern und einem Ganzzahlziel die Indizes der beiden Zahlen so zurück, dass sie sich zum Ziel addieren. Sie können davon ausgehen, dass jede Eingabe genau eine Lösung hat, und Sie können dasselbe Element nicht zweimal verwenden. Sie können die Antwort in beliebiger Reihenfolge zurückgeben.
Beispiel 1:
Eingabe: nums = [2,7,11,15], target = 9
Ausgabe: [0,1]
Beispiel 2:
Eingabe: nums = [3,2,4], target = 6
Ausgabe: [1,2]
Ich würde gerne Ihr Feedback / Vorschläge für Leistungsverbesserungen / andere Vorschläge hören. Hier ist der Link
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')
Leetcode-Statistiken:
Laufzeit: 772 ms, schneller als 36,98% der Python-Online-Einreichungen für Two Sum. Speichernutzung: 14,4 MB, weniger als 49,82% der Python-Online-Einreichungen für 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");
}
Leetcode-Statistiken:
Laufzeit: 384 ms, schneller als 34,03% der C ++ - Online-Einreichungen für Two Sum. Speichernutzung: 9,3 MB, weniger als 12,99% der C ++ - Online-Einreichungen für Two Sum.
Antworten
Ich bin kein Experte für C ++, kann aber ein Feedback zur Python-Lösung geben.
Ihre aktuelle Lösung läuft in \$O(n^2)\$. Grundsätzlich für jede Nummer ndes Eingangs nums, findet target - nin nums. Wie kann man es verbessern?
Der zweite Teil des Algorithmus kann von \ verbessert werden$O(n)\$zu \$O(1)\$. Anstatt target - nin einer Liste nachzuschlagen, können Sie ein Wörterbuch verwenden:
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
Ergebnisse:
Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB
Fügen Sie nur die Header-Dateien hinzu, die Sie benötigen
In Ihrer two_sum.hDatei benötigen Sie keine iostream, da Sie keine der Funktionen verwenden. Denken Sie daran, dass #includedie Datei buchstäblich kopiert und eingefügt wird. Wenn Sie diese Header-Datei in mehrere Dateien aufnehmen, kann dies möglicherweise die Kompilierungszeiten verlangsamen.
Geteilte Deklarationen und Definitionen
Normalerweise teilen Sie Ihre Dateien in zwei Teile: die Header-Datei (normalerweise endend mit *.h, *.hpp, *.hh) und die Quelldatei (normalerweise endend mit *.cpp, *.cc). Die Header-Datei besteht nur aus den Deklarationen und die Quelldatei enthält die Implementierung.
In Ihrem Fall sieht Ihre Header-Datei also folgendermaßen aus:
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
und Ihre Quelldatei sieht folgendermaßen aus:
two_sum.cpp
#include "two_sum.h"
std::vector<int> two_sum_solution(std::vector<int> &nums, int target)
{
...
}
Wenn Sie versuchen, Ihre two_sum.h(mit der Implementierung) in mehrere Dateien aufzunehmen, verstoßen Sie gegen die One-Definition-Regel . Ihre Quelldateien würden mehrere Definitionen derselben Funktion enthalten, und der Linker gibt einen Fehler aus. Eine Möglichkeit, sich fortzubewegen, besteht darin, die Funktionen zu markieren inline, aber Sie möchten höchstwahrscheinlich die ersteren ausführen.
Nein using namespacein den Header-Dateien
Nicht tun using namespaceoder eine seiner Varianten in einer Header-Datei. Da die Header-Datei in mehrere Quelldateien kopiert wird, kann dies zu störenden Fehlern führen. Siehe hier
Verwenden Sie die const-Referenz
Da two_sum_solutionder numsVektor nicht geändert wird, übergeben Sie ihn als const-Referenz.
size_t vs int für Array-Indizes
Verwenden Sie für Array-Indizes size_t anstelle von int
Verwenden Sie autoso viel wie möglich
Es gibt einige Fälle in Ihrem Code, in denen Sie autoden Typ verwenden können, anstatt ihn anzugeben. Beispiele:
auto match = target - nums[i];
auto v = two_sum_solution(v1, 22);
Die innerste Schleife ist sinnlos
Einfach machen
results.push_back(i);
results.push_back(j);
Wenn Sie die Lösung gefunden haben, möchten Sie das Ergebnis möglicherweise sofort zurückgeben.
Sie können die Leistung möglicherweise verbessern, indem Sie in der ersten Iteration über das angegebene Array eine Wertkarte -> Index erstellen.
Derzeit führt Ihr Programm Folgendes aus (zeitliche Komplexität):
- iteriere über alle
index, valuePaare des Arrays ( \$ O(n) \$) - Suche
target - valueim Array ( \$ O(n) \$) - Suchindex von
target - value( \$ O(n) \$)
Und da diese alle verschachtelt sind, gelangen Sie zu \$ O(n^2) \$(es ist nicht \$ n^3 \$ weil die letzte Suche nicht für jede Iteration durchgeführt wird).
Meine vorgeschlagene Lösung:
- Erstellen Sie eine Karte / ein Diktat von
{value: index}( \$ O(n) \$) - Iterieren Sie über das
index, valueArray ( \$ O(n) \$) - Suchen und geben Sie den Index von der Karte / dem Diktat zurück ( \$ 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
Das ist interessant für mich, weil ich einen C-Hintergrund habe und in den letzten Jahren angefangen habe, Python für die Arbeit zu verwenden. Ich hatte also den umgekehrten Weg wie Sie. Als ich Python gestartet habe, habe ich Lösungen wie Ihre sehr bevorzugt, weil das Durchlaufen von Listen so explizit und klar ist.
Seitdem habe ich jedoch gelernt, dass kompetentere Python-Programmierer bei der Arbeit meinen Code besser verstehen, wenn ich die Standardbibliothek verwende. Als ich anfing, in das Erlernen dieser Tools zu investieren, hatte dies den doppelten Effekt: 1) meinen Code prägnanter zu machen und 2) zeitlich und / oder räumlich effizienter zu sein.
In diesem Fall würde ich das Problem mit combinationsaus dem itertoolsPaket lösen :
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)
Es gibt wahrscheinlich eine noch prägnantere und klarere Lösung mit Numpy, einer Standardbibliothek in meiner Branche (Data Science), aber das stimmt nicht überall.
Eine Sache, die sich von Ihrem Code unterscheidet: Es gibt keinen Raum für Fehler, die nacheinander auftreten. Nach meiner Erfahrung Code wie dieser
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
ist für mich leicht zu schreiben, schwer zu lesen und die Wartbarkeit erstreckt sich über das gesamte Spiel von leicht bis unmöglich. Mit anderen Worten, die manuelle Verwaltung von Indizes in Python gibt mir gerade genug Seil, um mich daran zu hängen, und Standardbibliotheksfunktionen waren eine großartige Alternative.
Kennen Sie Ihre Container
std::unordered_mapist dein Freund in diesem Problem. Wenn Sie noch nie eine Nummer gesehen haben, verwenden Sie einfach die Funktion operator[]oder insert, um die Nummer und ihren Index hinzuzufügen. Bei Verwendung findwird ein Iterator zurückgegeben, bei dem es sich um ein key-valuePaar handelt.
z.B:
auto location = m.find(numToFind);
location->firstist dein Schlüssel und
location->secondist dein Wert
Verwenden Sie bei Ihrer Rückkehr keinen push_back
Sie können einfach eine Initialisierungsliste zurückgeben wie : {i,j}.