Two Sum
Bir tamsayı dizisi nums ve bir tamsayı target veriliyor. nums dizisinin farklı konumlarındaki tam olarak iki öğenin toplamı target değerine eşittir. Bu iki öğenin indislerini, küçük indis önce gelecek şekilde döndürün.
Fonksiyon
- numsinteger-array
- aranacak tamsayı dizisi
- targetinteger
- iki girdinin ulaşması gereken toplam
- Döndürürinteger-array
- iki indis, önce daha küçük olan
Kısıtlar
2 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109-109 ≤ target ≤ 109- Tam olarak bir farklı konum çifti, toplamda
targeteder.
Örnekler
- Girdi
- nums = [3, 8, 12, 5]target = 17
- Çıktı
- [2, 3]
- Açıklama
- 12, 2. indekste ve 5, 3. indekste bulunur; 12 + 5 = 17. Başka hiçbir çift 17'ye ulaşmaz.
- Girdi
- nums = [6, 1, 4, 10]target = 7
- Çıktı
- [0, 1]
- Açıklama
- 0. indeksteki 6 ile 1. indeksteki 1'in toplamı 7 eder: bu ikili ilk iki öğe olabilir.
- Girdi
- nums = [2, -6, 9, 4, 13]target = 3
- Çıktı
- [1, 2]
- Açıklama
- 1. indisteki -6 ile 2. indisteki 9'un toplamı 3 eder. Negatif sayılar, pozitif sayılarla aynı şekilde eşleşir.
Ek soru
nums zaten sıralanmış olarak gelseydi, yalnızca O(1) ek bellek kullanarak çifti O(n) zamanda bulabilir miydin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
İki iç içe döngüyle her çifti denemek doğrudur, ancak 10.000 sayı için bu yaklaşık 50 milyon kontrol demektir. Listeyi yeniden taramadan her sayının eşini bulabilir misin?
Bir
xdeğerinin üzerindeyken, çifti tamamlayacak değerin ne olduğunu zaten bilirsin: hedeftenxçıkarıldığında kalan değer. Tek soru, bu değerin yanından daha önce geçip geçmediğin ve hangi indekste olduğudur.Listeyi bir kez dolaş ve geçtiğin her değerin indeksini bir hash map'te tut. Her konumda önce eksik eşini ara; haritada varsa iki indekse de sahipsin. Aksi hâlde mevcut değeri kaydet ve devam et. Önce arayıp sonra kaydetmek, bir sayının kendisiyle eşleşmesini önler.
Çözüm
Her çifti kontrol etmek işe yarar, ancak işlem miktarı uzunluğun karesiyle birlikte artar. Soruyu tersine çevir: x sayısındayken, eşinin target - x olması gerektiğini zaten biliyorsun. Bir karma haritası, bu değeri daha önce görüp görmediğini sabit zamanda söyler; bu yüzden tek geçiş yeterlidir.
Her çifti kontrol et
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Bir ilk indeks i sabitleyin ve nums[i] + nums[j] değeri target değerine eşit olana kadar sağındaki her j indeksini deneyin. j değerini i + 1 noktasından başlatmak, bir konumun kendisiyle eşleşmesini önler, her çifti bir kez dener ve küçük indeksi önce koyar. Aradığınız çift, denediğiniz çiftlerden biridir; bu yüzden onu bulursunuz.
n sayı yaklaşık n²/2 çift oluşturur: n = 10^4, yaklaşık 5 × 10^7 toplama işlemi anlamına gelir.
Algoritma
numsiçindeki her indeks üzerindeidöngüsünü çalıştır.- Her
iiçin,jdöngüsünüi + 1değerinden son indekse kadar çalıştır. nums[i] + nums[j]değeritargetdeğerine eşitse,[i, j]değerini döndür.- Her iki döngü de tamamlanırsa boş bir dizi döndür. Problem, bunun hiçbir zaman gerçekleşmeyeceğini garanti eder.
def twoSum(nums, target):
n = len(nums)
for i in range(n):
# Only look at partners to the right, so each pair is checked once.
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []Bir hash map ile tek geçiş
Sezgi
Sabit bir nums[i] için, kaba kuvvet yönteminin iç döngüsü önceden bildiğin bir değeri arar: target - nums[i]. Bu tarama aslında gizli bir aramadır ve değerden indekse eşleme yapan bir karma harita, ortalama olarak sabit zamanda arama yapar.
Önce ara, sonra kaydet. Böylece bir sayı yalnızca kendisinden önce gelen bir sayıyla eşleşebilir, kendisiyle asla eşleşemez ve eşleştiği sayı her zaman daha önce olduğundan, onun indeksi önce gelir. Her sayı sabit zamanlı harita işlemleriyle bir kez ziyaret edilir, bu nedenle arama O(n) olur; bunun bedeli, en fazla n girdi içeren bir haritadır.
Algoritma
- Değerden indekse eşleyen boş bir harita oluştur.
- Her
iindeksi için, çifti tamamlayan değer olanneeddeğerini hesapla:targeteksinums[i]. needharitada varsa, kayıtlı indeksini ve ardındanideğerini döndür.- Aksi hâlde
nums[i]değeriniiindeksiyle birlikte kaydet ve devam et.
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
need = target - num
if need in seen:
return [seen[need], i]
seen[num] = i
return []
Tuzaklar ve uç durumlar
- Eşini aramadan önce bir sayıyı kaydetmek.
[4, 2, 6]vetarget = 8ile 4 kendisini bulur ve[0, 0]döndürürsün. - İndisleri yanlış sırada döndürmek. Önce arama, sonra kaydetme yapıldığında, eşlemdeki indis daha küçüktür ve ilk sırada gelir.
- İki işaretçi kullanmak için diziyi sıralayıp ardından sıralanmış kopyadaki konumları döndürmek. Her değerin özgün indisini yanında tut.
- Değerlerin pozitif veya birbirinden farklı olduğunu varsaymak.
target = 0için[0, 7, -3, 0]içindeki iki sıfır eşleşir:[0, 3]. - Lua ve R'de 1 tabanlı indisleri döndürmek. Her birinden 1 çıkar.
Sıkça sorulan sorular3
Two Sum'ın zaman karmaşıklığı nedir?
Hash map çözümü O(n) zamanda çalışır; çünkü her sayıyı bir kez ziyaret eder ve her arama veya ekleme işlemi ortalama olarak sabit zaman alır. Harita için O(n) ek alan kullanır. Her ikiliyi kontrol etmek O(n²) zaman ve O(1) alan alır.
Two Sum ek alan kullanmadan çözülebilir mi?
Sıralanmamış bir dizide doğrusal zamanda mümkün değildir. O(1) ek alanla her çifti kontrol etmeye geri dönersin; bu da O(n²) zaman alır. Hash map, doğrusal zaman karşılığında O(n) bellek kullanır.
Two Sum yinelenen sayıları nasıl işler?
Mevcut sayıyı kaydetmeden önce eşleşecek sayıyı aradığınızda tekrarlar işe yarar. target = 14 için [7, 3, 7] içinde ilk 7, 0. indekste kaydedilir ve ikinci 7 onu bulup [0, 2] sonucunu verir. Tek başına bir 7 kendisiyle eşleşmez: aradığınız sırada henüz haritada değildir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def twoSum(nums, target):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
nums = [3, 8, 12, 5] target = 17
Beklenen Çıktı
[2, 3]