Target Sum
Negatif olmayan tam sayılardan oluşan bir nums dizisi ve bir target tam sayısı veriliyor. Her sayının önüne bir artı veya eksi işareti koy, sıralarını koru ve ifadeyi hesapla. İfadeyi target değerine eşitleyen işaret seçimlerinin sayısını döndür. 2^n seçeneğin her biri ayrı ayrı sayılır; bu nedenle +0 ve -0 iki farklı seçimdir.
Fonksiyon
- numsinteger-array
- sayıların her biri bir işaret alır
- targetinteger
- ifadenin eşit olması gereken değer
- Döndürürinteger
- İfadesi hedefe eşit olan işaret seçeneği sayısı
Kısıtlar
1 ≤ nums.length ≤ 200 ≤ nums[i] ≤ 1000- The sum of
numsen fazla 1000'dir. -1000 ≤ target ≤ 1000- Yanıt en fazla 220'dir; 32 bitlik işaretli bir tamsayı sınırının oldukça içindedir.
Örnekler
- Girdi
- nums = [2, 1, 1]target = 2
- Çıktı
- 2
- Açıklama
+2 +1 -1ve+2 -1 +1ifadelerinin ikisi de 2'ye eşittir. 2'nin önünde eksi işareti olduğunda ulaşabileceğin en yüksek değer -2 + 1 + 1 = 0 olur, bu yüzden başka hiçbir seçenek işe yaramaz.
- Girdi
- nums = [0, 4, 4]target = 0
- Çıktı
- 4
- Açıklama
- İki 4'ün işaretleri zıt olmalı:
+4 -4veya-4 +4; her iki durumda da 0 her iki işareti de alabilir. Bu da 2 × 2 = 4 seçenek eder.
- Girdi
- nums = [6, 3]target = 4
- Çıktı
- 0
- Açıklama
- Dört olası değer 9, 3, -3 ve -9'dur. Bir işareti değiştirmek toplamı o sayının iki katı kadar değiştirir; bu nedenle 6 + 3 = 9 gibi tüm sonuçlar tektir ve çift hedef olan 4'e asla ulaşılamaz.
Ek soru
Toplama göre indekslenen hiçbir dizi belleğe sığmazken, değerleri 10^9'a kadar olan en fazla 40 sayıyı işleyebilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Her sayı için iki işareti de deneyebilirsin; bu,
2^nifade demektir. Birçok farklı işaret önekinin aynı geçerli toplamı verdiğine ve bundan sonra tamamen aynı şekilde ilerlediklerine dikkat et.Artı alan sayıların toplamına
P, eksi alan sayıların toplamınaNdiyelim.P - N = targetveP + N = sum(nums)olduğunu biliyorsun. Bu sanaPhakkında ne söyler?P = (sum + target) / 2, bu nedenle toplamı bu değere eşit olan alt kümeleri sayın.sdeğerine ulaşan alt kümelerin sayısını tutanways[s]dizisini kullanın ve her sayı için en büyüksdeğerinden başlayarak güncelleyin.sum + targettekse veya|target| > sumise hemen 0 döndürün.
Çözüm
Her sayının iki işareti vardır, dolayısıyla 2^n ifade bulunur. Konuma ve geçerli toplama göre saymak, aynı toplama ulaşan işaret öneklerini birleştirir. Daha da iyisi, artı işaretli sayılar sabit toplamlı bir alt küme oluşturur; böylece problem, O(n × S) zamanda (burada S, nums toplamıdır) belirli bir toplamı veren alt kümeleri sayma problemine dönüşür.
Her sayı için her iki işareti de dene
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Sayılar boyunca soldan sağa ilerleyip biriken toplamı tut ve her sayıda iki dala ayrıl: sayıyı ekle ya da çıkar. Her sayıya bir işaret verildiğinde, toplam target değerine eşitse 1 say. Her işaret seçimi tam olarak bir yoldur; bu yüzden sayıların toplamı yanıtı verir.
Her seçim için bir yaprak oluşur: 20 sayı için 2^20 ≈ 10^6 yaprak vardır ve eklenen her sayı işi iki katına çıkarır.
Algoritma
count(i, total)fonksiyonunu yazın; bu,i'den önceki sayıların toplamı zatentotalikennums[i..]dizisini işaretlemenin yollarının sayısıdır.i == nisetotal == targetolduğunda 1, aksi hâlde 0 döndürün.- Aksi hâlde
count(i+1, total + nums[i]) + count(i+1, total - nums[i])döndürün. - Cevap
count(0, 0)'dır.
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)Pozisyon ve geçerli toplamı önbelleğe al
Sezgi
count(i, total) yalnızca i ve total değerlerine bağlıdır; toplamı oluşturan işaretlere bağlı değildir. nums = [1, 1, 1, 1] için +1 -1 ve -1 +1 ön eklerinin ikisi de 2. konumda toplam 0'a ulaşır, dolayısıyla arama bu noktadan itibaren aynıdır. Her sonucu ilk kez hesaplandığında saklayın ve yeniden kullanın.
Geçerli toplam -S ile S arasında kalır; bu nedenle toplamı bir dizin olarak kullanmak için S kadar kaydırın: memo[i][total + S]. En fazla n × (2S+1) durum vardır; toplamı 1000 olan 20 sayı için bu yaklaşık 4 × 10^4 durum eder ve her biri sabit miktarda işlem gerektirir.
Algoritma
S = sum(nums)değerini hesaplayın ve -1 ile doldurulmuşn × (2S+1)boyutunda bir memo oluşturun.count(i, total)içinde, daha önce olduğu gibii == ndurumunda temel durumu döndürün.memo[i][total + S]değeri -1 ise, bunucount(i+1, total + nums[i]) + count(i+1, total - nums[i])ile doldurun.- Saklanan değeri döndürün ve
count(0, 0)çağrısını yapın.
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)Toplamı (S + hedef) / 2 olan alt kümeleri sayın
Sezgi
P, artı işaretli sayıların toplamı, N ise geri kalanların toplamı olsun. O hâlde P - N = target ve P + N = S, dolayısıyla 2P = S + target. Bir işaret seçimi, artı işaretli grubunun toplamı (S + target) / 2 olduğunda ve yalnızca o zaman geçerlidir; bu tür her alt küme bir işaret seçimine karşılık gelir.
ways[s], şimdiye kadar görülen sayıların toplamı s olan alt kümelerinin sayısını tutar ve başlangıç değeri ways[0] = 1 olur. Her x sayısı için, toplamı s olan bir alt küme ya x sayısını atlar ya da toplamı s - x olan bir alt kümeye bu sayıyı ekler. En büyük s değerinden başlayarak geriye doğru ilerle; böylece ways[s - x], x işlenmeden önceki değerini korur ve hiçbir sayı iki kez kullanılmaz. Bir 0, her girdiyi kendisine ekleyerek tüm sayıları ikiye katlar: sıfırın iki işareti vardır. Bu, en fazla 2 × 10^4 olmak üzere n × goal toplama işlemidir.
Algoritma
S = sum(nums)değerini hesapla. Eğer|target| > SveyaS + targettek ise 0 döndür.goal = (S + target) / 2olarak ayarla,goal + 1uzunluğunda sıfırlardan oluşanwaysoluştur veways[0] = 1olarak ayarla.numsiçindeki herxiçin,goaldeğerindenxdeğerine kadar azalan sırayla hersiçinways[s - x]değeriniways[s]değerine ekle.ways[goal]değerini döndür.
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]
Tuzaklar ve uç durumlar
- Eşlik kontrolünü atlamak.
[6, 3]ve hedef 4 için(9 + 4) / 2aşağı yuvarlanarak 6 olur ve{6}alt kümesi 0 yerine 1 verir. - Aralık kontrolünü atlamak.
[1, 2, 3]ve hedef -10 için(6 - 10) / 2 = -2, negatif bir dizi boyutu verir. waysdeğerini küçükten büyüğe doldurmak. Bu durumda bir sayı, kendisini zaten kullanan bir alt kümeye eklenir:[1, 3]ve hedef 2 için 1 yerine 2 sonucu bildirilir.- Sıfırı tek seçenek olarak değerlendirmek.
[0, 0, 0, 1, 0, 0]ve hedef -1 için, beş sıfırın her işaret örüntüsüne karşılık gelen 32 yanıt vardır. - Negatif bir geçerli toplamı memo dizisinde indis olarak kullanmak. Her toplamı
Skadar kaydır veya bir karma harita kullan.
Sıkça sorulan sorular3
Target Sum, alt küme toplamı problemiyle nasıl ilişkilidir?
Artı işaretli sayıların toplamı (S + target) / 2 olmalıdır; dolayısıyla yanıt, bu toplamı veren nums alt kümelerinin sayısıdır. Herhangi bir alt küme toplamı sayma DP'si, iki kontrol eklediğinizde bu problemi çözer: değer tam sayı olmalı ve |target|, S'yi aşmamalıdır.
Target Sum'ın zaman karmaşıklığı nedir?
Alt küme sayma DP'si, S nums toplamı olmak üzere O(n × S) zamanda ve O(S) bellekte çalışır. Önbelleğe alınmış özyineleme aynı zamana, ancak n × (2S+1) boyutunda bir tabloya sahiptir. Her işareti denemek O(2^n) sürer.
Target Sum, biriken toplamların tutulduğu bir hash haritasıyla çözülebilir mi?
Evet. Ulaşılabilir her birikimli toplamı, o toplama ulaşan işaret ön eklerinin sayısıyla eşleştirerek başlayın: {0: 1}. Her sayı için total + x ve total - x değerlerinden sonraki haritayı oluşturun. Yanıt, target değerindeki sayıdır. Bu, ileri yönde çalıştırılan, belleğe alınmış özyinelemedir ve yine O(n × S) zaman alır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def findTargetSumWays(nums, target):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
nums = [2, 1, 1] target = 2
Beklenen Çıktı
2