Two Sum
Sana tam sayılardan oluşan bir liste ve hedef bir değer veriliyor. Listedeki tam olarak iki sayı hedef değeri topluyor ve görevin bu sayıların hangi konumlarda bulunduğunu bildirmek.
nums = [3, 8, 12, 5] ve target = 17 değerlerini ele alalım. 12 değeri 2. indekste, 5 değeri ise 3. indekste bulunur ve 12 + 5 = 17 olduğundan yanıt [2, 3] olur.
İki sayı farklı konumlardan gelmelidir. [4, 2, 6] listesinde target = 8 iken 4'ü iki kez kullanmana izin verilmez; yanıt [1, 2] olur, çünkü 2 + 6 = 8. Ancak aynı değer listede iki kez bulunabilir: [7, 3, 7] listesinde target = 14 iken yanıt [0, 2] olur.
twoSum adında, bir tamsayı dizisi nums ve bir tamsayı target alan ve nums[i] + nums[j] değerinin target değerine eşit olduğu iki indeksten oluşan [i, j] dizisini döndüren bir fonksiyon yazın.
İndeksler farklı iki konumu göstermeli ve artan sırada döndürülmelidir (i, j'den küçüktür). Her girdide böyle tam olarak bir çift vardır.
Kısıtlamalar: 2 ≤ nums.length ≤ 10^4, -10^9 ≤ nums[i] ≤ 10^9, -10^9 ≤ target ≤ 10^9.
Fonksiyon
- arg1integer-array
- arg2integer
- Döndürürinteger-array
Örnekler
- Girdi
- arg1 = [3, 8, 12, 5]arg2 = 17
- Çıktı
- [2, 3]
- Girdi
- arg1 = [6, 1, 4, 10]arg2 = 7
- Çıktı
- [0, 1]
- Girdi
- arg1 = [2, -6, 9, 4, 13]arg2 = 3
- Çıktı
- [1, 2]
Gönderirken +13 gizli test
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
İç içe iki 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 hangisi olduğunu zaten bilirsin: hedeftenxçıkarıldığında kalan değer. Tek soru, bu değeri daha önce görüp görmediğin ve hangi indekste olduğudur.Listeyi bir kez dolaş ve geçtiğin her değeri indeksine eşleyen bir hash map tut. Her konumda önce eksik eşini ara; haritada varsa iki indekse de sahipsin. Aksi takdirde geçerli değeri kaydet ve devam et. Önce arama yapmak, bir sayının kendisiyle eşleşmesini engeller.
Bu problemin tam çözüm anlatımı yakında geliyor.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def twoSum(nums, target):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
arg1 = [3, 8, 12, 5] arg2 = 17
Beklenen
[2, 3]