3Sum

+10

Bir tamsayı listesi nums alıyorsunuz. nums içindeki üç farklı konumdan alınan ve a + b + c = 0 koşulunu sağlayan tüm değer üçlülerini [a, b, c] bulun. Her üçlüyü azalmayan sırada (a ≤ b ≤ c) yazın ve birden fazla konum seçimi aynı üçlüyü oluştursa bile her farklı üçlüyü yalnızca bir kez listeleyin. Üçlüleri önce ilk değerlerine, ardından ikinci değerlerine göre sıralı olarak döndürün.

Fonksiyon

threeSum(nums: integer-array) → integer-2d-array

numsinteger-array: en az üç öğe içeren tam sayılar listesi
Döndürürinteger-2d-array: toplamı 0 olan her farklı üçlü, her biri azalmayan sırada, liste sıralı

Kısıtlar

3 ≤ nums.length ≤ 3000
-10⁵ ≤ nums[i] ≤ 10⁵
En az bir üçlünün toplamı 0'dır.
İki üçlü, aynı üç değeri içeriyorsa aynıdır.

Örnekler

Girdi: nums = [-2, 0, 1, 1, -1, 2]
Çıktı: [[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
Açıklama: -2 + 0 + 2, -2 + 1 + 1 ve -1 + 0 + 1 işlemlerinin tümü 0 eder. [-2, 1, 1], 1 değerini iki kez kullanabilir çünkü 1 iki konumda bulunur; [-1, 0, 1] ise 1 değerlerinden herhangi biriyle oluşturulabilir ama yalnızca bir kez görünür.

Girdi: nums = [0, 0, 0, 0]
Çıktı: [[0, 0, 0]]
Açıklama: Dört sıfırdan herhangi üçü toplandığında 0 eder. Bu, konumlar için dört seçenek olduğu anlamına gelir, ancak hepsi aynı üçlüyü verdiğinden yanıt [0, 0, 0] değerini bir kez içerir.

Gönderirken +15 gizli test

Ek soru

Aynı kalıp 4Sum sorununu çözer: iki değeri sabitle ve geri kalanında iki işaretçi kullan. Bunu O(n³) zaman karmaşıklığında yazıp her seviyede yinelenen değer kurallarını doğru uygulayabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

İki şey 3Sum'ı göründüğünden daha zor hâle getirir. Her üçlüyü kontrol etmek O(n³) maliyetlidir ve değerler tekrar etse bile yanıt her üçlüyü yalnızca bir kez içermelidir. Sıralama her iki sorunu da çözer: eşit değerler yan yana gelir, böylece komşuları karşılaştırarak tekrarları atlarsın ve en küçük değer sabitlendiğinde diğer iki değer, sıralı bir listede iki işaretçinin tek geçişte çözdüğü bir çift toplamı problemine dönüşür.

Her üçlüyü de dene

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

Sezgi

Önce listeyi sırala. Ardından herhangi üç konum i < j < k, değerleri zaten sıralı olacak şekilde verir: nums[i] ≤ nums[j] ≤ nums[k]; böylece üçlü, onu bulduğun anda doğru sırada yazılır. İç içe üç döngü, konumların her seçimini gezer; dolayısıyla hiçbir üçlü gözden kaçmaz.

Şimdi tekrarlar. Sıralanmış ilk örnek [-2, -1, 0, 1, 1, 2] olur ve [-1, 0, 1] içindeki 1, 3. veya 4. indisten alınabilir. Bu nedenle her döngü, değeri aynı döngünün daha önce denediği değerle eşit olan bir konumu atlar. Böylece her döngü her farklı değeri bir kez dener ve her farklı üçlü, zaten sıralı biçimde bir kez elde edilir. Atlatma yalnızca aynı döngüdeki önceki konumla karşılaştırma yapar; bu nedenle [-2, 1, 1] yine iki tane 1 kullanır.

Sorun maliyettir. Yaklaşık n³/6 üçlü vardır: 3000 sayı için bu, 4.5 × 10^9 toplam demektir ve her türlü zaman sınırının çok ötesindedir.

Algoritma

nums dizisini sırala.
Pozisyonlar üzerinde i ile döngü kur ve nums[i], nums[i-1] değerine eşitse i değerini atla.
Bunun içinde, i+1 konumundan başlayarak j ile döngü kur ve j > i+1 ve nums[j], nums[j-1] değerine eşitse j değerini atla.
Bunun içinde, aynı atlama kuralıyla j+1 konumundan başlayarak k ile döngü kur ve üçü toplamda 0 ediyorsa [nums[i], nums[j], nums[k]] değerini kaydet.
Üçlüleri bulduğun sırayla döndür. Zaten sıralılar.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 1):
            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):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                if nums[i] + nums[j] + nums[k] == 0:
                    triplets.append([nums[i], nums[j], nums[k]])
    return triplets

Bir değeri sabitleyin, hash kümesiyle çifti bulun

Sezgi

İlk değer nums[i] sabitlendikten sonra, toplamları -nums[i] olan iki sonraki değere ihtiyacın var. Bu, Two Sum problemidir. j'yi i'nin sağına doğru ilerlet ve geçtiğin değerleri bir kümede tut. Her j için eksik değer need = -nums[i] - nums[j]'dir. need kümedeyse [nums[i], need, nums[j]] toplamı 0 eder. Kümede arama ortalama O(1) maliyetlidir; bu yüzden bir i için maliyet O(n), aramanın tamamı içinse O(n²)'dir.

Sıralama, yine de gerekli düzenlemeleri sağlar. Değeri bir öncekinin değerine eşit olan i'yi atla. Eşleşme bulduktan sonra j'yi, nums[j]'nin tüm kopyalarını geçecek şekilde ilerlet: ilk ve üçüncü değerler sabitken ortadaki değer de sabittir; dolayısıyla başka bir kopya yalnızca aynı üçlüyü tekrar eder. need, sıralı listenin daha önceki bir konumundan geldiğinden need ≤ nums[j] olur ve üçlü sıralı hâldedir. Ayrıca nums[i] > 0 olduğunda hemen durabilirsin: ondan sonraki iki değer en az onun kadar büyük olduğundan toplam 0 olamaz.

Bir ayrıntı: j sağa ilerledikçe nums[j] büyür ve need küçülür; bu yüzden bir i için bulunan üçlülerde ortadaki değer giderek azalır. [-2, -1, 0, 1, 1, 2] içinde, i = 0 iken önce ikinci 1'de [-2, 1, 1], ardından 2'de [-2, 0, 2] üçlüsünü bulursun. Her grubu yanıta eklemeden önce ters çevir. C ve R sürümleri, hash kümesi yerine görülen değerleri değere göre indekslenen bir dizide işaretler; bu yöntem, her değerin ±10^5 aralığında olması sayesinde çalışır.

Algoritma

nums'u sırala.
Her i için, nums[i] > 0 olduğunda dur ve nums[i], nums[i-1]'e eşitse i'yi atla.
Boş bir küme başlat. i+1'den başlayarak her j için need = -nums[i] - nums[j] değerini hesapla. need kümedeyse [nums[i], need, nums[j]] değerini kaydet ve j'yi nums[j]'nin kopyalarını geçecek şekilde ilerlet.
nums[j]'yi kümeye ekle ve sonraki j'ye geç.
Bu i için bulunan üçlüleri ters çevir ve yanıta ekle.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        group = []
        seen = set()  # values between position i and position j
        j = i + 1
        while j < n:
            need = -nums[i] - nums[j]
            if need in seen:
                group.append([nums[i], need, nums[j]])
                while j + 1 < n and nums[j + 1] == nums[j]:
                    j += 1
            seen.add(nums[j])
            j += 1
        # need shrinks as nums[j] grows, so this group came out backwards
        group.reverse()
        triplets.extend(group)
    return triplets

Sıralama yap ve iki işaretçi kullan

Sezgi

Sıralanmış dizi kümenin yerini alabilir. nums[i] değerini sabitle, lo değerini i+1 konumuna ve hi değerini son indekse koy ve nums[i] + nums[lo] + nums[hi] toplamına bak. Toplam 0'dan küçükse daha büyük bir değere ihtiyacın vardır, bu yüzden lo sağa ilerler. 0'dan büyükse daha küçük bir değere ihtiyacın vardır, bu yüzden hi sola ilerler. Toplam tam olarak 0 olduğunda üçlüyü kaydet ve her iki işaretçiyi de ilerlet.

Hiçbir üçlü kaybolmaz. Toplam 0'dan küçük olduğunda, nums[lo] geriye kalan en büyük değer olan nums[hi] ile bile yetersiz kalır; dolayısıyla aralıkta kalan hiçbir değerle eşleşemez ve onu elemek hiçbir şeyi kaybettirmez. 0'dan büyük olması bunun simetriğidir: nums[hi], geriye kalan en küçük değerle bile fazla büyüktür. Her adım bir değeri kalıcı olarak eler; bu nedenle bir i için en fazla n adım gerekir ve tüm arama O(n²) sürer; sıralama ve çıktı dışında bellek gerekmez.

Sıralanmış [-2, -1, 0, 1, 1, 2] dizisini ele al. i = 0 (değer -2) için lo -1'de, hi ise 2'de başlar: toplam -1'dir, bu yüzden lo 0'a ilerler. Şimdi -2 + 0 + 2 = 0 olduğundan [-2, 0, 2] değerini kaydedersin ve her iki işaretçi de iki 1'in üzerine gelir; bunlar da [-2, 1, 1] değerini verir. i = 1 (değer -1) için 0 ve 2'nin toplamı 1 eder; bu yüzden hi ikinci 1'e ilerler ve -1 + 0 + 1 = 0 olduğundan [-1, 0, 1] kaydedilir. i = 2 konumundaki 0 değeri hiçbir şey bulamaz; i = 3 konumundaki değer ise pozitif olduğundan arama durur.

Tekrarlanan değerler için iki kural gerekir. Değeri bir öncekiyle aynı olan bir i değerini atla. Eşleşme bulduktan sonra lo değerini, kullandığı değerin kopyalarını geçecek şekilde ilerlet. hi için ayrıca bir kurala gerek yoktur: lo daha büyük bir değere geldiğinde, eski nums[hi] değerinin bir kopyası artık 0'dan büyük bir toplam verir ve kendiliğinden uzaklaşır. i farklı değerleri artan sırayla ziyaret ettiğinden ve lo yalnızca sağa ilerlediğinden, üçlüler sıralı olarak elde edilir.

Algoritma

nums'u sırala.
Her i için, nums[i] > 0 olduğunda dur ve nums[i], nums[i-1]'e eşitse i'yi atla.
lo = i+1 ve hi = n-1 olarak ayarla. lo < hi olduğu sürece nums[i], nums[lo] ve nums[hi]'nin toplamını hesapla.
Toplam 0'dan küçükse lo'yu sağa kaydır. 0'dan büyükse hi'yi sola kaydır.
Toplam 0 ise üçlüyü kaydet, her iki işaretçiyi de ilerlet, ardından lo'yu kullandığı değerin kopyalarını geçecek şekilde ilerlet.
Üçlüleri döndür. Zaten sıralanmışlardır.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total < 0:
                lo += 1
            elif total > 0:
                hi -= 1
            else:
                triplets.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return triplets

Tuzaklar ve uç durumlar

Yanlış yanıtların çoğu yinelenen değerlerden kaynaklanır; bu nedenle bu değerleri içeren girdilerle test yapın.

nums[i], nums[i+1] değerine eşit olduğunda i konumunu atlamak, her değerin son kopyasını ilk öğe olarak bırakır ve ondan önceki kopyalar kaybolur. [-1, -1, 2] örneğinde bu, [-1, -1, 2] sonucunu kaybettirir. Bir önceki konumla, nums[i-1] ile karşılaştırın.
nums[i] > 0 yerine nums[i] ≥ 0 olduğunda durmak, [0, 0, 0] durumunu kaçırır.
Yinelenenleri atlamak yerine en sonda kaldırmak. 3000 sıfır olduğunda, iki işaretçili döngü herhangi bir temizleme yapılmadan önce [0, 0, 0] sonucunun milyonlarca kopyasını kaydeder ve çeşitli dillerde listelerden oluşan bir küme, listeleri kimliklerine göre karşılaştırır; bu yüzden kopyalar yine de kalır.
Aynı konumu iki kez kullanmak. Kümenin tamamını baştan listeyle dolduran bir hash kümesi çözümü, tek 1 değerini iki kez kullanarak [-2, 1, 3] dizisini [-2, 1, 1] hâline getirir. Yalnızca üzerinden daha önce geçtiğiniz konumlardaki değerlere bakın.
Üçlüleri sırasız döndürmek. Karşılaştırma birebir olduğundan hash kümesi çözümü her grubu tersine çevirmelidir; üçlüleri bir kümede toplayan bir çözüm de sonunda onları sıralamalıdır.

Sıkça sorulan sorular4

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

Sıralama ve iki işaretçi çözümü O(n²) zamanda çalışır. Sıralama O(n log n) maliyetlidir ve ilk değer için yapılan n seçimin her biri bir O(n) tarama gerektirir. Sıralama ve çıktı dışında O(1) ek alan kullanır. Her üçlüyü kontrol etmek ise bunun yerine O(n³) zaman alır.

3Sum yinelenen üçlülerden nasıl kaçınır?

Listeyi sıralar, böylece eşit değerler yan yana gelir. Ardından önceki değere eşit olan ilk değeri atlar ve her eşleşmeden sonra sol işaretçiyi kullandığı değerin kopyalarını geçecek şekilde ilerletir. Her üçlü, değerlerinin ilk kopyalarından başlayarak bir kez bulunur; bu nedenle sonuç kümelerine gerek yoktur.

3Sum için iki işaretçi mi yoksa bir hash kümesi mi kullanmalıyım?

Her ikisi de O(n²) zamanda çalışır. İki işaretçi ek bellek gerektirmez ve sıralı düzen, üçlüleri zaten sıralı olarak sunar. Bir karma kümesi O(n) bellek kullanır ve konumların birbirinden farklı olmasını ve çıktının sıralı olmasını sağlamak için dikkat gerektirir. Karma kümesi fikri, Two Sum örneğinde olduğu gibi sıralama yapamadığınızda ve özgün indisleri döndürmeniz gerektiğinde önemlidir.

3Sum, O(n²)'den daha hızlı çözülebilir mi?

Pek sayılmaz. Bilinen en iyi algoritmalar n² değerini yalnızca birkaç logaritmik çarpanla aşar ve hesaplamalı geometrideki birçok zorluk sonucu, hiçbir algoritmanın 2’nin altındaki bir n kuvvetine ulaşmadığını varsayar. Bu daha hızlı algoritmalar araştırma sonuçlarıdır; bu nedenle mülakatlarda beklenen yanıt O(n²)’dir.

Python

def threeSum(nums):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Girdi

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

Beklenen

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

3Sum

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her üçlüyü de dene

Bir değeri sabitleyin, hash kümesiyle çifti bulun

Sıralama yap ve iki işaretçi kullan

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler