Coding Interview Prep · Ders

İki Toplam ve Çeşitli Türevleri

Q: “İki Toplam ve Çeşitli Türevleri” dersi ücretsiz mi?

Evet — “İki Toplam ve Çeşitli Türevleri” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.

Q: Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.

Q: “İki Toplam ve Çeşitli Türevleri” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Q: Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Karma haritaları ve iki işaretçi kullanarak iki toplam, üç toplam, dört toplam ve sıralı dizide iki toplam problemlerini çözün; zaman ve alan maliyetlerini karşılaştırın.

İki Toplam ve Çeşitli Türevleri, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.

İki Toplam: Klasik Mülakat Problemi

LeetCode 1 "İki Toplam": sıralanmamış bir dizi ve bir hedef verildiğinde, toplamı hedefe eşit olan iki öğenin indislerini döndürünüz. Kaba kuvvet yaklaşımı olan O(n²), tüm çiftleri denetler. En iyi O(n) yaklaşımı bir karma harita kullanır: her x öğesi için target - x değerinin haritada zaten bulunup bulunmadığını denetleyiniz. Bulunuyorsa indis çiftini döndürünüz. Bulunmuyorsa x değerini ve indisini haritaya kaydediniz.

İki toplam, bir mülakattaki çoğu zaman ilk problemdir — bu problemi çok iyi bilmeniz, daha zor problemlere geçmeye hazır olduğunuzu gösterir.

def twoSum(nums, target):
    seen = {}   # val -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    return []

print(twoSum([2, 7, 11, 15], 9))   # [0, 1]
print(twoSum([3, 2, 4], 6))        # [1, 2]
print(twoSum([3, 3], 6))           # [0, 1]

Karma Harita İki Toplam İçin Neden Çalışır?

Karma harita, o ana kadar görülen her öğeyi depolar. x öğesi işlenirken target - x haritada bulunuyorsa, bu iki öğe geçerli bir çift oluşturur. Önemli nokta, tamamlayıcının x haritaya kaydedilmeden önce her zaman denetlenmesidir; böylece tek bir öğenin kendisiyle eşleştirilmesi önlenir (örneğin x == target/2 ise harita denetimi x kaydedilmeden önce yapılır ve iki kopya yoksa eşleşme gerçekleşmez).

# Trace two-sum on [2, 7, 11, 15], target=9
nums, target = [2, 7, 11, 15], 9
seen = {}
for i, x in enumerate(nums):
    complement = target - x
    print(f'i={i} x={x} complement={complement} seen={seen}')
    if complement in seen:
        print(f'  Found: indices [{seen[complement]}, {i}]')
        break
    seen[x] = i

Sıralı Dizide İki Toplam (İki İşaretçi)

Dizi zaten sıralıysa ve değerlerin indislerine (özgün indislerine değil) ihtiyacınız varsa iki işaretçi tekniğini kullanınız: karşı uçlardan başlayan sol ve sağ işaretçiler. Toplam hedefe eşitse döndürünüz. Toplam çok küçükse solu sağa ilerletiniz. Toplam çok büyükse sağı sola ilerletiniz. Bu yöntem O(n) zaman ve O(1) alan kullanır; dizi sıralı ve bellek kısıtlı olduğunda karma harita yaklaşımından daha iyidir.

def twoSumSorted(numbers, target):
    lo, hi = 0, len(numbers) - 1
    while lo < hi:
        s = numbers[lo] + numbers[hi]
        if s == target:
            return [lo + 1, hi + 1]   # 1-indexed as per LeetCode 167
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return []

print(twoSumSorted([2, 7, 11, 15], 9))   # [1, 2]
print(twoSumSorted([2, 3, 4], 6))         # [1, 3]
print(twoSumSorted([-1, 0], -1))          # [1, 2]

Üç Toplam (LeetCode 15)

LeetCode 15 "Üç Toplam": toplamı sıfır olan tüm benzersiz üçlüleri bulunuz. Diziyi sıralayınız, her seferinde bir öğeyi sabitleyiniz ve kalan sıralı alt diziye iki işaretçi uygulayınız. Yinelenen üçlüleri önlemek için yinelenen değerleri atlayınız. Zaman: O(n²) — çıktının kendisi O(n²) sayıda üçlü içerebileceği için bu problem açısından en iyi değerdir.

def threeSum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:  # skip duplicates
            continue
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s == 0:
                result.append([nums[i], nums[lo], nums[hi]])
                while lo < hi and nums[lo] == nums[lo+1]: lo += 1
                while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
                lo += 1; hi -= 1
            elif s < 0:
                lo += 1
            else:
                hi -= 1
    return result

print(threeSum([-1, 0, 1, 2, -1, -4]))  # [[-1,-1,2],[-1,0,1]]
print(threeSum([0, 0, 0, 0]))            # [[0,0,0]]

Dört Toplam (LeetCode 18)

LeetCode 18 "Dört Toplam": toplamı hedefe eşit olan tüm benzersiz dörtlüleri bulunuz. Üç toplamı genişletiniz: iki iç içe döngüyle iki öğeyi sabitleyiniz (yinelenenleri atlayarak), ardından iç alt diziye iki işaretçi uygulayınız. Zaman: O(n³). Genel olarak k-toplam için k-2 kez özyineleme yapıp ardından iki işaretçi uygulayınız; bu da O(n^(k-1)) zaman verir.

def fourSum(nums, target):
    nums.sort()
    n, result = len(nums), []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i+1, n-2):
            if j > i+1 and nums[j] == nums[j-1]:
                continue
            lo, hi = j+1, n-1
            while lo < hi:
                s = nums[i]+nums[j]+nums[lo]+nums[hi]
                if s == target:
                    result.append([nums[i],nums[j],nums[lo],nums[hi]])
                    while lo < hi and nums[lo] == nums[lo+1]: lo += 1
                    while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
                    lo += 1; hi -= 1
                elif s < target: lo += 1
                else: hi -= 1
    return result

print(fourSum([1,0,-1,0,-2,2], 0))
# [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Hedefe En Yakın İki Toplam

Yaygın bir çeşit şudur: toplamı hedefe en yakın olan çifti bulunuz (toplamın tam olarak hedefe eşit olması gerekmez). Diziyi sıralayınız ve iki işaretçi kullanınız. Şimdiye kadar görülen en yakın toplamı izleyiniz ve hedefle arasındaki mutlak fark daha küçük olan bir çift bulduğunuzda bu değeri güncelleyiniz. O(n log n) maliyetli bu yaklaşım, sıralamadan sonra doğrudan uygulanabilir.

def twoSumClosest(nums, target):
    nums.sort()
    lo, hi  = 0, len(nums) - 1
    best    = float('inf')
    best_pair = None
    while lo < hi:
        s = nums[lo] + nums[hi]
        if abs(s - target) < abs(best - target):
            best = s
            best_pair = (nums[lo], nums[hi])
        if s < target:
            lo += 1
        elif s > target:
            hi -= 1
        else:
            return best_pair  # exact match
    return best_pair

print(twoSumClosest([1, 3, 4, 7, 10], 15))  # (7, 10) => 17, closest to 15
print(twoSumClosest([2, 5, 8, 11], 10))     # (2, 8) => 10, exact!

Birden Çok Çiftle İki Toplam (Tüm Çiftler)

Toplamı hedefe eşit olan tüm çiftleri bulmak için diziyi sıralayınız ve iki işaretçi kullanarak tüm çiftleri toplayınız. Geçerli bir çift bulduktan sonra devam etmeden önce her iki uçtaki yinelenenleri atlayınız. Bu işlem sıralama için O(n log n), tarama için O(n) maliyet verir; toplam maliyet O(n log n) olur. Çiftleri toplamak için karma harita kullanmak da geçerlidir, ancak yinelenenler konusunda dikkatli olmanız gerekir.

def twoSumAllPairs(nums, target):
    nums.sort()
    lo, hi = 0, len(nums) - 1
    pairs  = []
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            pairs.append((nums[lo], nums[hi]))
            while lo < hi and nums[lo] == nums[lo+1]: lo += 1
            while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
            lo += 1; hi -= 1
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return pairs

print(twoSumAllPairs([1,1,2,3,4,4,5], 5))  # [(1,4),(1,4)-deduped,(2,3)]
# After duplicate-skipping: [(1,4),(2,3)]

K'den Küçük Toplamlı Çiftleri Sayma

Başka bir çeşit şudur: toplamı k'den küçük olan kaç çift bulunduğunu belirleyiniz. Diziyi sıralayınız ve iki işaretçi kullanınız. nums[lo] + nums[hi] < k olduğunda (lo, lo+1), (lo, lo+2), ..., (lo, hi) çiftlerinin tümü geçerlidir — yani hi - lo çift vardır. lo'yu ilerletiniz. Aksi durumda hi'yi küçültünüz. Toplam zaman: sıralama için O(n log n) ve sayma için O(n).

def countPairsLessThan(nums, k):
    nums.sort()
    lo, hi = 0, len(nums) - 1
    count  = 0
    while lo < hi:
        if nums[lo] + nums[hi] < k:
            count += hi - lo   # all (lo, lo+1)...(lo, hi) are valid
            lo += 1
        else:
            hi -= 1
    return count

print(countPairsLessThan([1, 3, 7, 11, 12], 10))  # (1,3),(1,7),(3,7) => 3
print(countPairsLessThan([3, 5, 2, 3], 7))         # (2,3),(2,3) => 2... verify

Karma Haritayla İki Toplam: Yinelenenleri Ele Alma

Aynı değer birden çok kez bulunabiliyor ve yalnızca varlığı değil, geçerli çiftlerin sayısını da bulmanız gerekiyorsa haritada sıklık sayılarını depolayınız. Her iki öğenin de eşit olduğu çiftlerde, sıklığı f olan bir değerden oluşabilecek çift sayısı f*(f-1)//2'dir. İki öğenin farklı olduğu çiftlerde sıklıkları birbiriyle çarpınız. Bu yöntem, tüm geçerli çiftleri O(n) zamanda saymanızı sağlar.

from collections import Counter

def countTwoSumPairs(nums, target):
    freq  = Counter(nums)
    count = 0
    seen  = set()
    for x in freq:
        y = target - x
        if y in freq and (x, y) not in seen:
            if x == y:
                count += freq[x] * (freq[x] - 1) // 2
            else:
                count += freq[x] * freq[y]
            seen.add((x, y))
            seen.add((y, x))
    return count

print(countTwoSumPairs([1,1,2,3,4,4,3], 4))
# Pairs summing to 4: (1,3)x2x2=4, (0+more)...

İki Toplam Deseninin Çeşitlerini Tanıma

İki toplam deseni birçok farklı biçimde karşınıza çıkar. Bir problem, sayısal bir ilişkiyi (toplam, çarpım veya fark) sağlayan iki ya da daha fazla öğe bulmanızı istediğinde bu deseni tanıyınız. Temel strateji her zaman aynıdır: bir öğeyi sabitleyiniz, ardından önceden hesaplanmış bir yapıda (karma harita veya sıralı dizi ve işaretçi) onun tamamlayıcısını bulunuz. İç içe döngülerle k-2 öğeyi sabitleyip temel durumu uygulayarak k-toplama genişletebilirsiniz.

# Summary of approaches by scenario
scenarios = [
    ('Unsorted array, any indices, one pair',   'hash map O(n) time O(n) space'),
    ('Sorted array, any indices, one pair',      'two pointers O(n) time O(1) space'),
    ('All unique pairs summing to target',        'sort + two pointers O(n log n)'),
    ('Three numbers summing to zero (3-sum)',     'sort + fix + two pointers O(n^2)'),
    ('k numbers summing to target (k-sum)',       'sort + k-2 loops + two pointers O(n^(k-1))')
]
for scenario, approach in scenarios:
    print(f'{scenario}\n  => {approach}\n')

İki Toplam İçin Mülakat İletişimi

Mülakatta iki toplam karşınıza çıktığında düşünme sürecinizi sesli olarak anlatınız: "Toplamı hedefe eşit olan iki sayıya ihtiyacım var. Her x sayısı için target-x değerinin mevcut olup olmadığını denetlemem gerekiyor. Bunu karma haritayla O(1) sürede yanıtlayabilirim; böylece toplam süre O(n), bellek kullanımı O(n) olur. Alternatif olarak dizi sıralıysa O(1) bellekle iki işaretçi kullanabilirim." Her iki yaklaşımı da belirtiniz ve seçim yapmadan önce bellek kısıtı olup olmadığını sorunuz.

Hızlı Kontrol

Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını ne kadar anladığınızı sınayın.

Ders Özeti

Bu derste şunları öğrendiniz: iki toplam, tamamlayıcının varlığını O(1) içinde kontrol etmek için bir karma tablo kullanır ve genel olarak O(n) sonuç verir, sıralı dizilerde iki işaretçi O(1) alan kullanır ve üç toplam ile dört toplam, sıralama ve iç içe döngüler aracılığıyla iki toplam problemine indirgenir; sırasıyla O(n²) ve O(n³) sürede çalışır. Sırada frekans sayımı örüntülerini ve varsayılan sözlük ile Counter kullanarak gruplamayı inceleyeceğiz.

Sıkça Sorulan Sorular