Target Sum
Du erhältst ein Array nums aus nicht negativen Ganzzahlen und eine Ganzzahl target. Setze vor jede Zahl ein Plus- oder Minuszeichen, behalte ihre Reihenfolge bei und werte den Ausdruck aus. Gib zurück, wie viele Vorzeichenkombinationen den Ausdruck gleich target machen. Jede der 2^n Kombinationen zählt für sich, daher sind +0 und -0 zwei verschiedene Möglichkeiten.
Funktion
- numsinteger-array
- die Zahlen, von denen jede ein Vorzeichen erhält
- targetinteger
- der Wert, dem der Ausdruck entsprechen muss
- Gibt zurückinteger
- die Anzahl der Vorzeichenkombinationen, deren Ausdruck dem Zielwert entspricht
Einschränkungen
1 ≤ nums.length ≤ 200 ≤ nums[i] ≤ 1000- Die Summe von
numsbeträgt höchstens 1000. -1000 ≤ target ≤ 1000- Die Antwort beträgt höchstens 220 und liegt damit deutlich innerhalb des Bereichs einer vorzeichenbehafteten 32-Bit-Ganzzahl.
Beispiele
- Eingabe
- nums = [2, 1, 1]target = 2
- Ausgabe
- 2
- Erklärung
+2 +1 -1und+2 -1 +1ergeben beide 2. Mit einem Minus vor der 2 ist das Höchste, was du erreichen kannst, -2 + 1 + 1 = 0, daher funktioniert keine andere Wahl.
- Eingabe
- nums = [0, 4, 4]target = 0
- Ausgabe
- 4
- Erklärung
- Die beiden 4er müssen entgegengesetzte Vorzeichen haben,
+4 -4oder-4 +4, und in beiden Fällen kann die 0 jedes der beiden Vorzeichen haben. Das ergibt 2 × 2 = 4 Möglichkeiten.
- Eingabe
- nums = [6, 3]target = 4
- Ausgabe
- 0
- Erklärung
- Die vier möglichen Werte sind 9, 3, -3 und -9. Das Ändern eines Vorzeichens verändert die Summe um das Doppelte dieser Zahl, daher ist jedes Ergebnis ungerade, wie bei 6 + 3 = 9, und das gerade Ziel 4 wird nie erreicht.
Weiterführende Frage
Kannst du bis zu 40 Zahlen mit Werten bis zu 10^9 verarbeiten, wenn kein nach der Summe indiziertes Array in den Speicher passt?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Du könntest für jede Zahl beide Vorzeichen ausprobieren, was
2^nAusdrücke ergibt. Beachte, dass viele verschiedene Vorzeichenpräfixe zur gleichen laufenden Summe führen und sich von da an genau gleich verhalten.Nenne
Pdie Summe der Zahlen, die ein Pluszeichen erhalten, undNdie Summe der Zahlen, die ein Minuszeichen erhalten. Du weißt, dassP - N = targetundP + N = sum(nums)gilt. Was sagt dir das überP?P = (sum + target) / 2, also zähle die Teilmengen vonnums, deren Summe diesen Wert ergibt. Speichere inways[s]die Anzahl der Teilmengen, dieserreichen, und aktualisiere den Wert für jede Zahl, beginnend beim größtensabwärts. Gib sofort 0 zurück, wennsum + targetungerade ist oder|target| > sum.
Lösung
Jede Zahl hat zwei Vorzeichen, also gibt es 2^n Ausdrücke. Beim Zählen nach Position und laufender Summe werden Vorzeichenpräfixe zusammengeführt, die dieselbe Summe erreichen. Noch besser: Die Zahlen mit positivem Vorzeichen bilden eine Teilmenge mit einer festen Summe. Damit wird das Problem zu einer Zählung von Teilmengen mit einer gegebenen Summe, in O(n × S) Zeit, wobei S die Summe von nums ist.
Probiere beide Vorzeichen für jede Zahl aus
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Gehe die Zahlen von links nach rechts mit einer laufenden Summe durch und verzweige bei jeder Zahl zweimal: Addiere sie oder subtrahiere sie. Wenn jede Zahl ein Vorzeichen hat, zähle 1, wenn die Summe gleich target ist. Jede Vorzeichenwahl entspricht genau einem Pfad, also ergeben die Anzahlen zusammen die Antwort.
Das ist ein Blatt pro Wahl: 2^20 ≈ 10^6 Blätter bei 20 Zahlen, und jede zusätzliche Zahl verdoppelt den Aufwand.
Algorithmus
- Schreibe
count(i, total), die Anzahl der Möglichkeiten,nums[i..]mit Vorzeichen zu versehen, wenn die Zahlen voribereits die Summetotalergeben. - Wenn
i == ngilt, gib 1 zurück, wenntotal == targetgilt, andernfalls 0. - Andernfalls gib
count(i+1, total + nums[i]) + count(i+1, total - nums[i])zurück. - Die Antwort ist
count(0, 0).
def findTargetSumWays(nums, target):
n = len(nums)
def count(i, total):
# Ways to sign nums[i:] so that the whole expression ends at target
if i == n:
return 1 if total == target else 0
return count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
return count(0, 0)Memoisierung nach Position und laufender Summe
Idee
count(i, total) hängt nur von i und total ab, nicht von den Vorzeichen, die zu total geführt haben. Bei nums = [1, 1, 1, 1] erreichen die Präfixe +1 -1 und -1 +1 an Position 2 beide den Gesamtwert 0, daher ist die Suche ab dort dieselbe. Speichere jedes Ergebnis beim ersten Mal und verwende es wieder.
Die laufende Summe bleibt zwischen -S und S, daher verschiebe sie um S, um sie als Index zu verwenden: memo[i][total + S]. Es gibt höchstens n × (2S+1) Zustände, etwa 4 × 10^4 bei 20 Zahlen, deren Summe 1000 beträgt, jeweils mit konstantem Aufwand.
Algorithmus
- Berechne
S = sum(nums)und erstelle einn × (2S+1)-Memo, das mit -1 gefüllt ist. - Gib in
count(i, total)wie zuvor den Basisfall beii == nzurück. - Wenn
memo[i][total + S]-1 ist, fülle es mitcount(i+1, total + nums[i]) + count(i+1, total - nums[i]). - Gib den gespeicherten Wert zurück und rufe
count(0, 0)auf.
def findTargetSumWays(nums, target):
n = len(nums)
whole = sum(nums)
# memo[i][total + whole]: ways for nums[i:] from this running total, -1 while unknown
memo = [[-1] * (2 * whole + 1) for _ in range(n)]
def count(i, total):
if i == n:
return 1 if total == target else 0
if memo[i][total + whole] == -1:
memo[i][total + whole] = count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
return memo[i][total + whole]
return count(0, 0)Anzahl der Teilmengen mit der Summe (S + target) / 2
Idee
Sei P die Summe der Zahlen mit Pluszeichen und N die Summe der übrigen Zahlen. Dann gilt P - N = target und P + N = S, also 2P = S + target. Eine Vorzeichenwahl funktioniert genau dann, wenn ihre Plusgruppe die Summe (S + target) / 2 hat, und jede solche Teilmenge entspricht einer Vorzeichenwahl.
ways[s] zählt die Teilmengen der bisher betrachteten Zahlen, deren Summe s beträgt; zu Beginn gilt ways[0] = 1. Für jede Zahl x gilt: Eine Teilmenge mit Summe s überspringt entweder x oder fügt es zu einer Teilmenge mit Summe s - x hinzu. Gehe s von der größten Zahl abwärts durch, damit ways[s - x] weiterhin seinen Wert von vor x enthält und keine Zahl zweimal verwendet wird. Eine 0 addiert jeden Eintrag zu sich selbst und verdoppelt so alle Anzahlen: die beiden Vorzeichen einer Null. Das sind n × goal Additionen, höchstens 2 × 10^4.
Algorithmus
- Berechne
S = sum(nums). Wenn|target| > SoderS + targetungerade ist, gib 0 zurück. - Setze
goal = (S + target) / 2, erstellewaysmitgoal + 1Nullen und setzeways[0] = 1. - Für jedes
xinnumsaddiere fürsvongoalabwärts bisxways[s - x]zuways[s]. - Gib
ways[goal]zurück.
def findTargetSumWays(nums, target):
whole = sum(nums)
# plus - minus = target and plus + minus = whole, so plus = (whole + target) / 2
if abs(target) > whole or (whole + target) % 2 == 1:
return 0
goal = (whole + target) // 2
# ways[s]: how many subsets of the values seen so far add up to s
ways = [0] * (goal + 1)
ways[0] = 1
for x in nums:
# From the top down, so each value is used at most once
for s in range(goal, x - 1, -1):
ways[s] += ways[s - x]
return ways[goal]
Stolperfallen und Grenzfälle
- Die Paritätsprüfung überspringen. Für
[6, 3]und das Ziel 4 wird(9 + 4) / 2auf 6 abgerundet, und die Teilmenge{6}ergibt 1 statt 0. - Die Bereichsprüfung überspringen. Für
[1, 2, 3]und das Ziel -10 ist(6 - 10) / 2 = -2, eine negative Arraygröße. waysvon unten nach oben füllen. Eine Zahl wird dann einer Teilmenge hinzugefügt, die sie bereits verwendet:[1, 3]mit dem Ziel 2 ergibt 2 statt 1.- Eine Null als eine Auswahl behandeln.
[0, 0, 0, 1, 0, 0]mit dem Ziel -1 hat 32 Lösungen, eine für jedes Vorzeichenmuster der fünf Nullen. - Ein Memo anhand einer negativen laufenden Summe indizieren. Verschiebe jede Summe um
Soder verwende eine Hash-Map.
Häufige Fragen3
Wie hängt Target Sum mit dem Teilmengensummenproblem zusammen?
Die Zahlen mit einem Pluszeichen müssen die Summe (S + target) / 2 ergeben. Die Antwort ist also die Anzahl der Teilmengen von nums mit dieser Summe. Ein beliebiger DP-Algorithmus zum Zählen von Teilmengensummen löst das Problem, sobald du zwei Prüfungen hinzufügst: Der Wert muss eine ganze Zahl sein und |target| darf S nicht überschreiten.
Wie hoch ist die Zeitkomplexität von Target Sum?
Die DP zum Zählen von Teilmengen benötigt O(n × S) Zeit und O(S) Speicher, wobei S die Summe von nums ist. Die Rekursion mit Memoisierung benötigt dieselbe Laufzeit, aber eine Tabelle der Größe n × (2S+1). Alle Vorzeichen auszuprobieren, benötigt O(2^n).
Kann man Target Sum mit einer Hash-Map der laufenden Summen lösen?
Ja. Ordne jeder erreichbaren laufenden Summe die Anzahl der Vorzeichenpräfixe zu, die sie erreichen, beginnend mit {0: 1}, und erstelle für jede Zahl aus total + x und total - x die nächste Map. Die Antwort ist der Zähler bei target. Das ist die memoized Rekursion vorwärts ausgeführt, mit derselben Laufzeit von O(n × S).
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def findTargetSumWays(nums, target):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argumente
nums = [2, 1, 1] target = 2
Erwartete Ausgabe
2