Beachten Sie, dass es drei Array-Listen gibt, die jeweils die gleiche Länge haben und in ihnen positiv, negativ und null sind. Ich musste ein Programm schreiben, um Kombinationen zu finden, deren Summe auf Null kommt. Also im Grunde, wenn die Arrays waren: -
%Vor%O / P: A [0] + B [0] + C [0], A [2] + B [2] + C [2] usw.
Ich könnte auf zwei Arten denken, 1. Haben Sie 3 for Schleifen und berechnen Sie die Summe mit [i] + b [j] + c [k], wenn Null den Index drucken. Großes O wird O sein (N ^ 3) 2. Verwenden Sie zwei for-Schleife, aber verwenden Sie Binärsuche, um das dritte Element zu finden, das die Summe als Null geben würde. Großes O ist O (N ^ 2LogN)
Irgendwelche anderen Möglichkeiten?
Danke.
BEARBEITEN: Basierend auf den unten angegebenen Antworten ist meine erste Lösung die schnellstmögliche. Aber wenn die Frage darin besteht, die Anzahl der Kombinationen zu finden und NICHT auszudrucken, dann lesen Sie bitte unten die Antwort von Grigor Gevorgyan.
Kann in O (n ^ 2) mit der Methode 2 pointers durchgeführt werden.
Sortieren Sie die Arrays. Jetzt mach folgendes:
Legen Sie ans = 0 fest.
Führen Sie eine externe Schleife durch das Array a mit dem Index i . Setzen Sie nun j = 0, k = n - 1 .
Schauen Sie sich sum = a [i] + b [j] + c [k] an
Wenn Summe & lt; 0 , erhöhen j .
Wenn Summe & gt; 0 verringern k .
Wenn sum == 0 , suchen Sie den Bereich von Elementen, die gleich b [j] und
Dies funktioniert, weil Arrays sortiert sind und die Addition eine lineare Funktion ist.
Der interne Teil wird in O (n) mit einer Gesamtanzahl von O (n ^ 2) ausgeführt.
Beispielcode in C ++:
%Vor%Hinweis : Das Sortieren des Arrays a ist nicht notwendig, nur um es gut aussehen zu lassen:)
Ich denke das 3SUM:
Um die wikipedia Writeup zu zitieren:
Es gibt einen einfachen Algorithmus, um 3SUM in O (n2) -Zeit zu lösen, indem man zuerst jedes Element im Array hasht, alle möglichen Paare findet und schließlich die Existenz des verbleibenden Wertes überprüft (was einfach das Negative der Summe von ist jedes Paar) mit der Hash-Tabelle.
Der naive Ansatz wäre, alle Teilmengen zu überprüfen, aber das hat eine sehr schlechte Laufzeit. Ссылка Ohne weitere Einschränkung glaube ich, dass dies das Gesamtproblem der NP-Teilmenge ist. Es gibt eine Lösung im Zusammenhang mit dem Rucksackproblem, das eine anständige Lösung bietet. Ссылка
Müssen Sie alle Kombinationen finden, die zu 0 oder nur einer einzigen oder nur einer Lösung mit 3 Elementen summieren?
Lösungen sollten {{A [0]}, {B [0]}, {C [0]}, {C [2]}, {A [0], B [0]}, {A [ 0], B [0], C [0]}, {A [0], B [0], C [0], C [2]}, {A [1], B [1], A [2 ]}, {A [2], B [2]} und so weiter}
Diese Lösung beschleunigt sich nur, wenn Sie Daten in Array-Listen aus einem Speicher, z. Datei oder ein beliebiger Eingabestream von Ihnen selbst. Durch Ersetzen der dritten Array-Liste durch hashtable erhalten Sie eine konstante Zeit, um eine dritte Komponente der Nullsumme nachzuschlagen. In Ihren beiden verschachtelten Schleifen wird jedes Mal, wenn Sie das neue Paar a[i]+b[j] erhalten, in der Hashtabelle nach c[n0]=-a[i]+b[j] gesucht, die O(1) benötigt. Die gesamte Zeitkomplexität ist also O (n ^ 2). Lassen Sie mich klarstellen, dass diese Lösung nur hilft, wenn Sie mit dem Lesevorgang fertig werden dürfen und nichts beschleunigt, wenn Sie bereits mit Array-Listen versehen sind.
Tags und Links algorithm