4Sum

Q: 4Sum'ın zaman karmaşıklığı nedir?

O(n³). İki döngü yaklaşık n²/2 çift seçer (i, j) ve her biri en fazla n adımlık bir çift işaretçi taraması yapar; O(n log n) sıralama bunun yanında küçüktür.

Q: 4Sum'ı kSum'a nasıl genellersiniz?

Sıralı bir liste üzerinde kSum(nums, target, k) yazın. k = 2 için iki işaretçili tarama yapar. Daha büyük bir k için ilk değer üzerinde döngüye girer, tekrarları atlar ve sağdaki değerler üzerinde k-1 ve target - nums[i] ile kendisini çağırır. Her seviye n çarpanı ekler, dolayısıyla kSum O(n^(k-1)) maliyetindedir.

Q: 4Sum O(n²) sürede çözülebilir mi?

n²/2 çift toplamını bir karma eşlemede gruplayabilir ve her çifti, toplamı target değerinden kendi toplamı çıkarıldığında elde edilen değere eşit olan çiftlerle eşleştirebilirsiniz. Bu yöntem, aynı toplamı paylaşan çift sayısı az olduğunda hızlıdır; ancak tek bir toplam O(n²) çift içerebilir, dolayısıyla en kötü durum O(n³)'ten daha iyi değildir.

Ortaİki işaretçi Sıralama

+10

Bir tamsayı listesi nums ve bir tamsayı target veriliyor. Dört değeri de nums listesinin farklı konumlarında bulunan ve toplamları target olan tüm dörtlüleri [a, b, c, d] döndürün. Her dörtlüyü, değerleri azalmayan sırada olacak şekilde yazın. Aynı dört değer farklı konumlardan seçilebiliyorsa dörtlü yine de yalnızca bir kez yer alır. Yanıtı önce ilk değere, sonra ikinciye, ardından üçüncüye göre sıralayın. Hiçbir dörtlü koşulu sağlamıyorsa boş bir liste döndürün.

Fonksiyon

fourSum(nums: integer-array, target: integer) → integer-2d-array

numsinteger-array: seçilecek sayılar, en az bir
targetinteger: her dörtlünün ulaşması gereken toplam
Döndürürinteger-2d-array: toplamı hedefe eşit olan farklı dörtlüler; her biri sıralıdır, liste de sıralıdır; hiçbiri yoksa boş liste

Kısıtlar

1 ≤ nums.length ≤ 200
-10⁸ ≤ nums[i] ≤ 10⁸
-10⁹ ≤ target ≤ 10⁹
Dört değerin toplamı -4 × 10⁸ ile 4 × 10⁸ arasında kalır, bu nedenle 32 bitlik bir tamsayıya sığar.
Dört değerin aynısını içeren dörtlüler bir tane sayılır.

Örnekler

Girdi: nums = [3, -1, 0, 2, -2, 1, -3]target = 1
Çıktı: [[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]
Açıklama: Dört dörtlünün her birinin toplamı 1 eder; örneğin -3 + (-1) + 2 + 3. -3 ile başlayan ikisi önce gelir ve ikinci değerlerine göre sıralanır: -1, 0'dan önce gelir.

Girdi: nums = [4, 4, 4, 4, 4, 4]target = 16
Çıktı: [[4, 4, 4, 4]]
Açıklama: Altı konum arasından seçilebilecek 15 dört konum seçeneğinin her biri, toplamı 16 olan dört tane 4 verir; bu nedenle [4, 4, 4, 4] bir kez görünür.

Girdi: nums = [1, 5, 2, 9]target = 3
Çıktı: []
Açıklama: Tek seçenek dört sayının tamamıdır ve 1 + 5 + 2 + 9 = 17, 3 değil; bu yüzden cevap boş bir listedir.

Ek soru

Farklı dörtlüleri değil, değerleri target değerini veren dört konum kümesini sayın. İkinci örnekte sonuç 15'tir. Bunu O(n²) içinde yapabilir misiniz?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Dört konumdan oluşan her kümeyi kontrol etmek O(n⁴) maliyetlidir ve yinelenen değerler aynı dörtlüyü birçok kez oluşturur. 3Sum indirgemesini bir düzey daha derine uygulayın: sıralayın, iki döngüyle ilk iki değeri sabitleyin, son çifti iki işaretçiyle bulun ve her düzeyde yinelenen değerleri atlayın.

Dört öğeden oluşan her kümeyi deneyin

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Önce sıralayın; böylece i < j < k < l konumları değerleri azalmayan sırada tutar ve her dörtlü doğru sırayla yazılır. İç içe dört döngü, dört konumun her seçimine ulaşır. Tekrarları önlemek için bir döngü, bir sonraki konumunda bir adım önce denediği değer varsa ilerler. Altı tane 4 olduğunda her döngü yalnızca ilk konumunu dener; böylece [4, 4, 4, 4] 15 kez yerine bir kez elde edilir.

200 sayı için 64,684,950 tane dörtlü küme vardır ve n iki katına çıktığında bu sayı yaklaşık 16 kat artar.

Algoritma

nums dizisini sırala.
i < j < k < l üzerinde dört iç içe döngü kur; her biri kendisini çevreleyen döngünün başlangıcından bir sonraki konumdan başlasın.
Her döngüde, döngünün ilk konumu olmayan ve bir önceki konumla aynı değeri taşıyan bir konumu atla.
Dördünün toplamı target olduğunda [nums[i], nums[j], nums[k], nums[l]] değerini kaydet. Döngüler bunları sıralı düzende üretir.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # same second value as the round before
            for k in range(j + 1, n - 1):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                for l in range(k + 1, n):
                    if l > k + 1 and nums[l] == nums[l - 1]:
                        continue  # same fourth value as the round before
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        quads.append([nums[i], nums[j], nums[k], nums[l]])
    return quads

Sıralama, iki döngü, iki işaretçi

Sezgi

nums[i] ve nums[j] sabitleyince geriye bir çift sorusu kalır: j'nin sağındaki ve toplamı target - nums[i] - nums[j] olan iki değeri bul. Sıralı bir listede tek bir tarama yeterlidir. lo'yu j+1 konumuna, hi'yi ise son indekse ayarla. Toplam target'dan küçükse lo'yu sağa ilerlet; büyükse hi'yi sola ilerlet.

Her hamle, hiçbir yanıtta yer alamayacak bir değeri eler. Toplam çok küçükse geriye kalan en büyük değer olan nums[hi] bile nums[lo] için yeterli değildir; bu yüzden nums[lo] elenebilir. Toplam çok büyük olduğunda da aynı mantıkla nums[hi] elenir. Bir (i, j) çifti en fazla n hamle gerektirir; dolayısıyla n²/2 çiftin maliyeti O(n³) olur.

İlk örnekte, i -3'ün ve j -1'in üzerindeyken lo, 0'dan 1'i geçip 2'ye ilerler; burada -3 + (-1) + 2 + 3 = 1 olur.

Algoritma

nums dizisini sırala.
Her i için, i > 0 olduğunda ve nums[i], nums[i-1] değerine eşit olduğunda bu adımı atla.
i sonrasındaki her j için, j > i+1 olduğunda ve nums[j], nums[j-1] değerine eşit olduğunda bu adımı atla.
lo = j+1 ve hi = n-1 olarak ayarla. lo < hi olduğu sürece, dört değerin toplamını target ile karşılaştır: daha küçükse lo'yu sağa, daha büyükse hi'yi sola kaydır.
Eşleşme varsa dörtlüyü kaydet, her iki işaretçiyi de ilerlet, ardından lo tuttuğu değeri gösterdiği sürece lo'yu ilerlet.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # this second value was already handled
            lo, hi = j + 1, n - 1
            while lo < hi:
                total = nums[i] + nums[j] + nums[lo] + nums[hi]
                if total < target:
                    lo += 1
                elif total > target:
                    hi -= 1
                else:
                    quads.append([nums[i], nums[j], nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
    return quads

Tuzaklar ve uç durumlar

nums[j], nums[j-1]'ye eşit olduğunda j'yi atlamak. j = i+1 olduğunda karşılaştırılan değer, i'nin kullandığı değerdir; bu yüzden hedef 8 iken [2, 2, 2, 2, 2], [2, 2, 2, 2]'yi gözden kaçırır.
3Sum'ın nums[i] > target erken çıkışını kopyalamak. [-5, -4, -3, -2, -1] ve hedef -10 için döngü -5'te durur ve [-4, -3, -2, -1]'i gözden kaçırır.
Dörtten kısa listeler. Bir veya iki sayı olduğunda n-3 negatiftir: Swift'te 0..<(n - 3) çalışma zamanı hatasına yol açar ve Rust'ta usize türündeki n - 3 taşmaya uğrar. Önce boş bir liste döndürün.
Dörtlüleri bir hash kümesinde toplamak ve sıralanmamış hâlde döndürmek.

Sıkça sorulan sorular3

4Sum'ın zaman karmaşıklığı nedir?

O(n³). İki döngü yaklaşık n²/2 çift seçer (i, j) ve her biri en fazla n adımlık bir çift işaretçi taraması yapar; O(n log n) sıralama bunun yanında küçüktür.

4Sum'ı kSum'a nasıl genellersiniz?

Sıralı bir liste üzerinde kSum(nums, target, k) yazın. k = 2 için iki işaretçili tarama yapar. Daha büyük bir k için ilk değer üzerinde döngüye girer, tekrarları atlar ve sağdaki değerler üzerinde k-1 ve target - nums[i] ile kendisini çağırır. Her seviye n çarpanı ekler, dolayısıyla kSum O(n^(k-1)) maliyetindedir.

4Sum O(n²) sürede çözülebilir mi?

n²/2 çift toplamını bir karma eşlemede gruplayabilir ve her çifti, toplamı target değerinden kendi toplamı çıkarıldığında elde edilen değere eşit olan çiftlerle eşleştirebilirsiniz. Bu yöntem, aynı toplamı paylaşan çift sayısı az olduğunda hızlıdır; ancak tek bir toplam O(n²) çift içerebilir, dolayısıyla en kötü durum O(n³)'ten daha iyi değildir.

def fourSum(nums, target):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

nums = [3, -1, 0, 2, -2, 1, -3]
target = 1

Beklenen Çıktı

[[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]