Target Sum
Otrzymujesz tablicę nums zawierającą nieujemne liczby całkowite oraz liczbę całkowitą target. Umieść znak plusa lub minusa przed każdą liczbą, zachowaj ich kolejność i oblicz wartość wyrażenia. Zwróć liczbę wyborów znaków, dla których wyrażenie jest równe target. Każdy z 2^n wyborów liczy się osobno, więc +0 i -0 to dwa różne wybory.
Funkcja
- numsinteger-array
- liczby, z których każda otrzymuje znak
- targetinteger
- wartość, której musi być równe wyrażenie
- Zwracainteger
- liczba wyborów znaku, których wyrażenie jest równe wartości docelowej
Ograniczenia
1 ≤ nums.length ≤ 200 ≤ nums[i] ≤ 1000- Suma
numswynosi co najwyżej 1000. -1000 ≤ target ≤ 1000- Odpowiedź wynosi najwyżej 220, znacznie poniżej zakresu 32-bitowej liczby całkowitej ze znakiem.
Przykłady
- Wejście
- nums = [2, 1, 1]target = 2
- Wyjście
- 2
- Wyjaśnienie
+2 +1 -1i+2 -1 +1są równe 2. Z minusem przy 2 największy wynik, jaki możesz uzyskać, to -2 + 1 + 1 = 0, więc żaden inny wybór nie zadziała.
- Wejście
- nums = [0, 4, 4]target = 0
- Wyjście
- 4
- Wyjaśnienie
- Dwie czwórki muszą mieć przeciwne znaki,
+4 -4lub-4 +4, a w obu przypadkach 0 może mieć dowolny znak. To daje 2 × 2 = 4 możliwości.
- Wejście
- nums = [6, 3]target = 4
- Wyjście
- 0
- Wyjaśnienie
- Cztery możliwe wartości to 9, 3, -3 i -9. Zmiana znaku zmienia sumę o dwukrotność tej liczby, więc każdy wynik jest nieparzysty, tak jak 6 + 3 = 9, a parzysty cel 4 nigdy nie zostaje osiągnięty.
Pytanie dodatkowe
Czy poradzisz sobie z maksymalnie 40 liczbami o wartościach do 10^9, gdy żadna tablica indeksowana sumą nie zmieści się w pamięci?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Możesz wypróbować oba znaki dla każdej liczby, co daje
2^nwyrażeń. Zauważ, że wiele różnych prefiksów znaków prowadzi do tej samej sumy bieżącej i od tego momentu zachowują się dokładnie tak samo.Oznaczmy przez
Psumę liczb, którym przypisano plus, a przezNsumę liczb, którym przypisano minus. Wiadomo, żeP - N = targetorazP + N = sum(nums). Co możesz z tego wywnioskować oP?P = (sum + target) / 2, więc policz podzbiorynums, których suma jest równa tej wartości. Przechowujways[s], czyli liczbę podzbiorów, których suma wynosis, i aktualizuj tę wartość dla każdej liczby, zaczynając od największegosi schodząc w dół. Od razu zwróć 0, gdysum + targetjest nieparzyste lub|target| > sum.
Rozwiązanie
Każda liczba ma dwa możliwe znaki, więc istnieje 2^n wyrażeń. Zliczanie według pozycji i bieżącej sumy łączy prefiksy znaków, które prowadzą do tej samej sumy. Jeszcze lepiej: liczby ze znakiem plus tworzą podzbiór o ustalonej sumie, więc problem sprowadza się do zliczania podzbiorów o danej sumie w czasie O(n × S), gdzie S jest sumą nums.
Wypróbuj oba znaki dla każdej liczby
Poprawne, ale nie kończy się na największych testach
Intuicja
Przejdź przez liczby od lewej do prawej, prowadząc bieżącą sumę i rozgałęziając się dwukrotnie przy każdej z nich: dodaj ją albo ją odejmij. Gdy każda liczba będzie miała znak, policz 1, jeśli suma jest równa target. Każdy wybór znaku to dokładnie jedna ścieżka, więc liczby ścieżek sumują się do odpowiedzi.
To jeden liść na każdy wybór: 2^20 ≈ 10^6 liści dla 20 liczb, a każda dodatkowa liczba podwaja nakład pracy.
Algorytm
- Zapisz
count(i, total), czyli liczbę sposobów na przypisanie znaków donums[i..], gdy liczby przedimają już sumętotal. - Jeśli
i == n, zwróć 1, gdytotal == target, a w przeciwnym razie 0. - W przeciwnym razie zwróć
count(i+1, total + nums[i]) + count(i+1, total - nums[i]). - Odpowiedzią jest
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)Zapamiętuj na podstawie pozycji i sumy bieżącej
Intuicja
count(i, total) zależy tylko od i i total, a nie od znaków, które dały w wyniku tę sumę. Dla nums = [1, 1, 1, 1] prefiksy +1 -1 i -1 +1 dają sumę 0 na pozycji 2, więc dalsze wyszukiwanie przebiega tak samo. Zapisz każdy wynik przy pierwszym obliczeniu i używaj go ponownie.
Bieżąca suma mieści się w zakresie od -S do S, więc dodaj do niej S, aby użyć jej jako indeksu: memo[i][total + S]. Istnieje najwyżej n × (2S+1) stanów, czyli około 4 × 10^4 dla 20 liczb, których suma wynosi 1000, a każdy z nich wymaga stałej liczby operacji.
Algorytm
- Oblicz
S = sum(nums)i utwórz tablicę memo o wymiarachn × (2S+1), wypełnioną wartościami -1. - W
count(i, total)zwróć przypadek bazowy dlai == n, tak jak wcześniej. - Jeśli
memo[i][total + S]ma wartość -1, wypełnij ją wynikiemcount(i+1, total + nums[i]) + count(i+1, total - nums[i]). - Zwróć zapisaną wartość i wywołaj
count(0, 0).
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)Policz podzbiory, których suma wynosi (S + target) / 2
Intuicja
Niech P będzie sumą liczb ze znakiem plus, a N sumą pozostałych. Wówczas P - N = target oraz P + N = S, więc 2P = S + target. Wybór znaków jest poprawny dokładnie wtedy, gdy suma grupy z plusem wynosi (S + target) / 2, a każdy taki podzbiór odpowiada jednemu wyborowi znaków.
ways[s] zlicza podzbiory liczb rozpatrzonych do tej pory, których suma wynosi s, zaczynając od ways[0] = 1. Dla każdej liczby x podzbiór o sumie s albo pomija x, albo dodaje ją do podzbioru o sumie s - x. Przechodź od największego s w dół, aby ways[s - x] nadal miało wartość sprzed rozpatrzenia x i żadna liczba nie została użyta dwukrotnie. Zero dodaje każdą wartość do samej siebie, podwajając wszystkie liczności: odpowiada to dwóm znakom dla zera. To n × goal dodań, najwyżej 2 × 10^4.
Algorytm
- Oblicz
S = sum(nums). Jeśli|target| > SlubS + targetjest nieparzyste, zwróć 0. - Ustaw
goal = (S + target) / 2, utwórzwayszawierającegoal + 1zer i ustawways[0] = 1. - Dla każdego
xwnums, dlasodgoalw dół dox, dodajways[s - x]doways[s]. - Zwróć
ways[goal].
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]
Pułapki i przypadki brzegowe
- Pominięcie sprawdzenia parzystości. Dla
[6, 3]i celu 4 wyrażenie(9 + 4) / 2zaokrągla się w dół do 6, a podzbiór{6}daje 1 zamiast 0. - Pominięcie sprawdzenia zakresu. Dla
[1, 2, 3]i celu -10 wyrażenie(6 - 10) / 2 = -2oznacza ujemny rozmiar tablicy. - Wypełnianie
waysod dołu do góry. Liczba dołącza wtedy do podzbioru, który już jej używa: dla[1, 3]i celu 2 zwracane są 2 zamiast 1. - Traktowanie zera jako jednego wyboru.
[0, 0, 0, 1, 0, 0]z celem -1 ma 32 odpowiedzi — po jednej dla każdego układu znaków pięciu zer. - Indeksowanie tablicy memo ujemną sumą bieżącą. Przesuń każdą sumę o
Salbo użyj mapy mieszającej.
Najczęstsze pytania3
Jaki związek ma Target Sum z problemem sumy podzbioru?
Liczby ze znakiem plus muszą sumować się do (S + target) / 2, więc odpowiedzią jest liczba podzbiorów nums o takiej sumie. Rozwiązuje to każde programowanie dynamiczne zliczające sumy podzbiorów, gdy dodasz dwa warunki: wartość musi być liczbą całkowitą, a |target| nie może przekraczać S.
Jaka jest złożoność czasowa problemu Target Sum?
Programowanie dynamiczne do zliczania podzbiorów działa w czasie O(n × S) i zużywa O(S) pamięci, gdzie S jest sumą nums. Rekurencja z memoizacją ma taką samą złożoność czasową, ale wykorzystuje tablicę o wymiarach n × (2S+1). Sprawdzanie wszystkich znaków ma złożoność O(2^n).
Czy problem Target Sum można rozwiązać za pomocą mapy haszującej z bieżącymi sumami?
Tak. Przypisz każdej osiągalnej sumie bieżącej liczbę prefiksów znaków, które do niej prowadzą, zaczynając od {0: 1}, i utwórz następną mapę na podstawie total + x oraz total - x dla każdej liczby. Odpowiedzią jest liczba przy target. To rekurencja z memoizacją wykonywana w przód, w tym samym czasie O(n × S).
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def findTargetSumWays(nums, target):
# Napisz kod tutajTest #1
Test #2
Test #3
Argumenty
nums = [2, 1, 1] target = 2
Oczekiwany wynik
2