İki sayının toplamı

Problem

Bir tamsayı dizisi ve bir hedef değer veriliyor. Dizide toplamı tam olarak hedefe eşit olan iki farklı konumdaki elemanı bul ve bu iki elemanın index'lerini döndür. Girdide böyle bir çiftin tam olarak bir tane olduğu garanti ediliyor; aynı index'i iki kez kullanamazsın ama aynı değer dizide iki kez geçiyorsa ikisini birlikte kullanabilirsin. Index'lerin hangi sırayla döndüğü önemli değil.

Girdi:  nums = [4, 9, 13, 2], target = 11
Çıktı:  [1, 3]          (9 + 2 = 11)

Girdi:  nums = [5, 5], target = 10
Çıktı:  [0, 1]          (aynı değer, farklı index)

Netleştirme soruları

• Çözüm her zaman var mı? Yoksa ne dönmeliyim: boş dizi, null, exception, Optional?
• Birden fazla çift varsa herhangi biri mi, yoksa hepsi mi isteniyor?
• Dizi sıralı mı? (Sıralıysa iki işaretçi O(1) bellekle çözer.)
• Değer aralığı ne? target - nums[i] int'te taşabilir mi? (LeetCode sınırlarında, ±10⁹, taşmaz.)
• Negatif sayı ve sıfır olabilir mi?
• Index mi değer mi döndürmeliyim? (Sıralayıp çözmek index'leri kaybettirir.)

İpuçları

Yaklaşım

Brute force: Tüm (i, j) çiftlerini iç içe döngüyle dene, toplamı hedefe eşit olanı döndür. O(n²) zaman, O(1) bellek. n = 10⁴ için 5×10⁷ karşılaştırma; çalışır ama mülakatçı hemen "daha iyisini yapabilir misin?" diye sorar.

Sırala + iki işaretçi: Sıralarsan iki uçtan içeri yürüyerek O(n log n) zamanda bulursun. Ama problem index istiyor; sıralama index'leri karıştırır, (değer, index) çiftlerini sıralaman gerekir. Daha karmaşık ve daha yavaş.

Optimal, tek geçişli hash map: Darboğaz "eşi daha önce gördüm mü?" sorusu. Map<Integer, Integer> (değer → index) ile bu soru ortalama O(1) olur. Diziyi soldan sağa gezerken her eleman için önce target - nums[i] map'te var mı diye bakarsın; varsa cevap bulundu. Yoksa elemanı map'e eklersin. Neden doğru: cevap çifti (i, j) ve i < j ise, j'ye gelindiğinde nums[i] zaten map'tedir; ilk eleman ikinciyi değil, ikinci eleman birinciyi bulur.

Ekleme sırası önemli: önce ekleyip sonra ararsan [3, ...] ve target = 6 için 3 kendisiyle eşleşir. Tekrar eden değerlerde (örn. [5, 5]) map'te ilk 5'in index'i durur, ikinci 5 onu bulur; üzerine yazma sorunu oluşmaz çünkü cevap yazmadan önce kontrol edilir.

Java çözümü

import java.util.HashMap;
import java.util.Map;

public final class TwoSum {

    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> indexByValue = new HashMap<>();      // değer -> index
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            Integer partner = indexByValue.get(complement);
            if (partner != null) {
                return new int[]{partner, i};
            }
            indexByValue.put(nums[i], i);                          // kendisiyle eşleşmesin diye sonra ekle
        }
        throw new IllegalArgumentException("no two elements sum to " + target);
    }
}

Karmaşıklık

• Zaman: O(n) ortalama. Her eleman için bir get ve bir put, ikisi de ortalama O(1). En kötü durumda (aşırı çakışma) Java 8+ treeify sayesinde bucket başına O(log n), toplam O(n log n).
• Bellek: O(n). En kötü durumda çift dizinin sonunda bulunur ve n-1 eleman map'e girer.
• Integer boxing sabit çarpanı artırır; çok büyük girdide primitive bir hash map (ör. Eclipse Collections IntIntHashMap) kullanılabilir, mülakatta söylemek yeterli.

Kenar durumlar ve testler

Çözüm sınıfı, küçük bir main ile JDK 21'de derlendi ve aşağıdaki durumlar doğrulandı. Ek olarak 2.000 rastgele girdide (bilinen bir çift yerleştirilerek) dönen index'lerin farklı olduğu ve toplamının hedefe eşit olduğu kontrol edildi.

Çözüm yoksa ne döneceği bir tasarım kararıdır. Burada sözleşme "çözüm var" dediği için ihlali exception ile bildirdim; production kodunda Optional<int[]> daha okunaklı olur.

Mülakatçı için

Bu soru genelde ısınma sorusudur; 15 dakikada bitmesi beklenir ve asıl sinyal adayın ne kadar hızlı brute force'tan hash map'e geçtiği ve ince noktaları kendiliğinden söyleyip söylemediğidir. Aday sessizce doğrudan optimal kodu yazıyorsa ezberden geliyor olabilir; "neden önce arayıp sonra ekliyorsun?" diye sorarak anlayıp anlamadığını kontrol et.

İpucu zamanlaması: 3-4 dakika içinde brute force'tan öteye geçemezse ilk ipucunu ("her elemanın eşi belli") ver. Map fikri gelip "kendisiyle eşleşme" hatası çıkarsa doğrudan söyleme; [3, 2, 4], 6 örneğini kodla birlikte yürütmesini iste.

Takip soruları:

1. Dizi sıralı olsaydı ne değişirdi? (Beklenen: iki işaretçi, O(1) bellek; LeetCode 167.)
2. Tüm farklı değer çiftlerini döndürmen gerekseydi? (Beklenen: tekrarları atlama stratejisi; bkz. 3Sum.)
3. Dizi tek makineye sığmayacak kadar büyük ve diskte duruyorsa? (Beklenen: değer aralığına göre bölümleme; [a, b] aralığındaki değerlerin eşleri [target - b, target - a] aralığında olduğu için her bölüm yalnızca karşılık gelen bölümle birlikte belleğe alınır. Alternatif: dış sıralama (external sort) + iki işaretçi.)

Benzer problemler

• Two Sum II - Input Array Is Sorted (LeetCode 167): sıralı girdi, iki işaretçi.
• 3Sum (LeetCode 15): sırala, bir eleman sabitle, kalan iki işaretçi (bu sette: 3sum).
• Subarray Sum Equals K (LeetCode 560): aynı "daha önce gördüm mü" fikri, önek toplamlarına uygulanmış (bu sette: subarray-sum-equals-k).
• Two Sum IV - Input is a BST (LeetCode 653).