Two Sum II: Sorted Input

Q: Sıralanmış bir dizideki İki Toplam problemi için iki işaretçi neden işe yarar?

İki uçtaki değerlerin toplamı çok küçük olduğunda, sağ uç hâlâ oyunda olan değerlerin en büyüğü olduğundan, sol değer kalan her eş için çok küçüktür. Bu değeri kalıcı olarak eleyebilirsin. Aynı mantık, toplam çok büyük olduğunda sağ değeri eler. Cevap çifti hiçbir zaman elenmez; bu yüzden işaretçiler onun üzerinde sonlanır.

Q: Two Sum II'nin zaman karmaşıklığı nedir?

İki işaretçili çözüm O(n) zamanda ve O(1) ek alanla çalışır: her adımda işaretçilerden biri içeri doğru hareket eder ve en fazla n-1 adım sonra buluşurlar. Her eş için ikili arama yapmak O(n log n) zaman alır, tüm çiftleri kontrol etmek ise O(n²) zaman alır.

Q: Neden ilk Two Sum örneğindeki gibi bir hash map kullanmıyoruz?

Bir hash map işe yarar ve O(n) zamanda çalışır, ancak en fazla n değer saklar. Sıralı düzen bu belleği gereksiz kılar: iki işaretçi yalnızca toplama bakarak hangi yöne ilerleyeceklerini bilir. Görüşmeciler, size verilen sıralamadan yararlanıp yararlanmadığınızı görmek için bu sürümü sorar.

Q: Burada ikili arama ne zaman daha iyi bir seçimdir?

Bir değer sabit olduğunda ve yalnızca eşini bulmanız gerektiğinde. numbers[0] çiftin içinde olmalıysa, bir ikili arama diğer indeksi O(log n) içinde bulur. Bilinmeyen bir çifti bulmak için iki işaretçili tarama, n ayrı aramadan daha hızlıdır.

Kolayİki işaretçi İkili arama

+10

Az tamsayı dizisi numbers sana azalmayan sırada sıralanmış olarak verilir ve bir tamsayı target verilir. Farklı konumlardaki tam olarak bir çift değer, toplamı target olacak şekildedir. Bu iki konumu 0 tabanlı indeksler olarak, küçük indeks önce gelecek şekilde döndür.

Fonksiyon

twoSumSorted(numbers: integer-array, target: integer) → integer-array

numbersinteger-array: sıralanmış tamsayı dizisi
targetinteger: iki değerin ulaşması gereken toplam
Döndürürinteger-array: i < j ve numbers[i] + numbers[j] == target koşulunu sağlayan 0 tabanlı iki indeks [i, j]

Kısıtlar

2 ≤ numbers.length ≤ 10⁴
-5 × 10⁸ ≤ numbers[i] ≤ 5 × 10⁸
-10⁹ ≤ target ≤ 10⁹
numbers azalmayan sırada sıralanmıştır.
Tam olarak bir indeks çifti i < j, numbers[i] + numbers[j] == target koşulunu sağlar.

Örnekler

Girdi: numbers = [-4, 1, 3, 8, 12]target = 9
Çıktı: [1, 3]
Açıklama: 1, 1. indekste ve 8, 3. indekste bulunur; 1 + 8 = 9. Başka hiçbir çift 9'a ulaşmaz: örneğin, -4 + 12 = 8.

Gönderirken +13 gizli test

Ek soru

Ekstra bellek kullanımı O(1) olacak şekilde O(n) zamanda çözebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bir hash map, sıralanmamış sürümü tek geçişte çözer, ancak O(n) bellek kullanır. Burada dizi sıralıdır ve bu sıralama hangi yönde ilerlemeniz gerektiğini gösterir. Her iki uca da birer işaretçi koyun. Toplam çok küçükse yalnızca daha büyük bir sol değer yardımcı olabilir; çok büyükse yalnızca daha küçük bir sağ değer yardımcı olabilir. Her adımda bir değer kesin olarak elenir, bu nedenle tek bir geçişte fazladan bellek kullanmadan çifti bulabilirsiniz.

Her çifti kontrol et

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

Sezgi

Her i < j konum çiftini deneyin ve numbers[i] + numbers[j] değerinin target değerine eşit olup olmadığını test edin. i soldan başlayıp ilerlediği ve j onun hemen sonrasından başladığı için bulduğunuz ilk çiftte küçük indeks zaten ilk sıradadır.

Bu doğru, ancak sıralı olma özelliğini göz ardı ediyor. n = 10^4 olduğunda yaklaşık 5 × 10^7 çift vardır ve yanıt dizinin sonlarına yakınsa neredeyse hepsini test edersiniz. Bu, büyük testler için çok yavaştır.

Algoritma

Her indeks için i üzerinde döngü yapın.
i+1 değerinden son indekse kadar j üzerinde döngü yapın.
numbers[i] + numbers[j], target değerine eşitse [i, j] döndürün.

def twoSumSorted(numbers, target):
    n = len(numbers)
    for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i, j]
    return []

Her ortak için ikili arama

Sezgi

İlk değer olan numbers[i] değerini sabitlediğinde, eşinin ne olduğunu tam olarak bilirsin: target - numbers[i]. Dizinin i indeksinin sağındaki kısmı sıralıdır, bu nedenle ikili arama bu eşin orada olup olmadığını O(log n) adımda bulabilir.

[-4, 1, 3, 8, 12] ve target = 9 için: i = 0 iken eş 13 olurdu, ancak bu değer yoktur. i = 1 iken eş 8'dir ve arama onu 3. indekste bulur. Yanıt [1, 3] olur.

Yalnızca i indeksinin sağında arama yapmak, küçük indeksin önce gelmesini sağlar ve bir değerin kendisiyle eşleşmesini önler. Çift tektir, bu nedenle eş değeri bu aralıkta en fazla bir kez görünür ve bulunan herhangi bir eşleşme yanıttır. Toplamda: her biri O(log n) süren n arama.

Algoritma

i değerini 0'dan n-2'ye kadar döngüye sokun.
need = target - numbers[i] değerini hesaplayın.
i+1 ile n-1 arasındaki indekslerde need için ikili arama yapın.
Değeri mid konumunda bulursanız [i, mid] döndürün.

def twoSumSorted(numbers, target):
    n = len(numbers)
    for i in range(n - 1):
        need = target - numbers[i]
        lo, hi = i + 1, n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if numbers[mid] == need:
                return [i, mid]
            if numbers[mid] < need:
                lo = mid + 1
            else:
                hi = mid - 1
    return []

Her iki uçtan iki işaretçi

Sezgi

left = 0 ve right = n-1 ile başlayıp numbers[left] + numbers[right] değerine bak. target değerine eşitse işlem tamamdır. Çok küçükse numbers[left] yanıtın bir parçası olamaz: hâlâ değerlendirmedeki en büyük değerle eşleştirildiğinde bile toplam hedefin altında kalır. Bu yüzden left değerini sağa kaydır. Toplam çok büyükse numbers[right] da yanıtın parçası olamaz; çünkü geriye kalan en küçük eş değerle bile hedef aşılır. Bu yüzden right değerini sola kaydır.

Her hamle, çiftte asla yer alamayacak bir değeri eler ve çiftin kendisi asla elenmez. İşaretçiler en fazla n-1 hamleden sonra buluşur; dolayısıyla tarama O(n) zaman alır ve iki değişken kullanır.

target = 9 için [-4, 1, 3, 8, 12] üzerinde: -4 + 12 = 8 çok küçüktür, bu yüzden left 1. indekse ilerler. Ardından 1 + 12 = 13 çok büyüktür, bu yüzden right 3. indekse ilerler. Şimdi 1 + 8 = 9 olur ve yanıt [1, 3] şeklindedir.

Algoritma

left değerini 0, right değerini ise n-1 olarak ayarlayın.
left < right olduğu sürece total = numbers[left] + numbers[right] değerini hesaplayın.
total, target değerine eşitse [left, right] değerini döndürün.
total daha küçükse left değerini 1 artırın; daha büyükse right değerini 1 azaltın.

def twoSumSorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1  # need a bigger sum
        else:
            right -= 1  # need a smaller sum
    return []

Tuzaklar ve uç durumlar

İki işaretçili döngü kısa olduğundan, hatalar etrafındaki ayrıntılarda gizlenir.

1 tabanlı konumlar döndürmek. Bu sürüm 0 tabanlı indeksler ister: [-4, 1, 3, 8, 12] ve target = 9 için yanıt [2, 4] değil, [1, 3] olur. Lua ve R'de döndürmeden önce 1 çıkarın.
left <= right koşuluyla döngü kurmak. İşaretçiler buluştuğunda toplam, aynı değeri iki kez kullanır.
Yanlış işaretçiyi hareket ettirmek. Çok küçük bir toplam daha büyük bir değer gerektirir ve bunu yalnızca left sağlayabilir.
Yinelenen değerleri reddetmek. target = 4 için [2, 2, 5, 7] dizisindeki iki 2 de kullanılır; bunlar farklı konumlardadır.
Taşma. Buradaki sınırlar, her toplamın 32 bitlik bir tamsayı içinde kalmasını sağlar. Değerler 10^9 seviyesine ulaşabilseydi, bunları 64 bitlik bir türde toplardınız.

Sıkça sorulan sorular4

Sıralanmış bir dizideki İki Toplam problemi için iki işaretçi neden işe yarar?

İki uçtaki değerlerin toplamı çok küçük olduğunda, sağ uç hâlâ oyunda olan değerlerin en büyüğü olduğundan, sol değer kalan her eş için çok küçüktür. Bu değeri kalıcı olarak eleyebilirsin. Aynı mantık, toplam çok büyük olduğunda sağ değeri eler. Cevap çifti hiçbir zaman elenmez; bu yüzden işaretçiler onun üzerinde sonlanır.

Two Sum II'nin zaman karmaşıklığı nedir?

İki işaretçili çözüm O(n) zamanda ve O(1) ek alanla çalışır: her adımda işaretçilerden biri içeri doğru hareket eder ve en fazla n-1 adım sonra buluşurlar. Her eş için ikili arama yapmak O(n log n) zaman alır, tüm çiftleri kontrol etmek ise O(n²) zaman alır.

Neden ilk Two Sum örneğindeki gibi bir hash map kullanmıyoruz?

Bir hash map işe yarar ve O(n) zamanda çalışır, ancak en fazla n değer saklar. Sıralı düzen bu belleği gereksiz kılar: iki işaretçi yalnızca toplama bakarak hangi yöne ilerleyeceklerini bilir. Görüşmeciler, size verilen sıralamadan yararlanıp yararlanmadığınızı görmek için bu sürümü sorar.

Burada ikili arama ne zaman daha iyi bir seçimdir?

Bir değer sabit olduğunda ve yalnızca eşini bulmanız gerektiğinde. numbers[0] çiftin içinde olmalıysa, bir ikili arama diğer indeksi O(log n) içinde bulur. Bilinmeyen bir çifti bulmak için iki işaretçili tarama, n ayrı aramadan daha hızlıdır.

Python

def twoSumSorted(numbers, target):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

numbers = [-4, 1, 3, 8, 12]
target = 9

Beklenen

[1, 3]

Two Sum II: Sorted Input

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her çifti kontrol et

Her ortak için ikili arama

Her iki uçtan iki işaretçi

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler