Tarkibga o'tish

Ikki son yig'indisi (Two Sum)

Butun sonlar ro'yxati va maqsad yig'indi berilgan. Yig'indisi maqsadga teng bo'lgan ikkita son indeksini toping. Har bir kirishda aynan bitta yechim mavjud deb hisoblanadi. Bir elementni ikki marta ishlatib bo'lmaydi.

nums = [2, 7, 11, 15],  target = 9
Javob: [0, 1]   →   nums[0] + nums[1] = 2 + 7 = 9

nums = [3, 2, 4],  target = 6
Javob: [1, 2]   →   nums[1] + nums[2] = 2 + 4 = 6

nums = [3, 3],  target = 6
Javob: [0, 1]   →   nums[0] + nums[1] = 3 + 3 = 6

Bu masala juda ko'p intervyularda uchraydi, lekin uning qiymati yechimning o'zida emas — u hashlashning "komplement" shablonini noto'g'ri O(n²) yondashuvdan O(n) ga qanday o'tkazishni ko'rsatadi.

Birinchi yondashuv: barcha juftliklar

Ro'yxatdagi har ikkita elementning yig'indisi maqsadga teng emas-emasligini tekshirish:

FUNCTION TWO_SUM_BRUTE(nums, target)
    FOR i = 0 DAN n-1 GACHA
        FOR j = i+1 DAN n-1 GACHA
            IF nums[i] + nums[j] = target
                RETURN [i, j]
    RETURN []

Bu har juftlikni tekshiradi. n ta elementda n*(n-1)/2 ta juftlik — O(n²) vaqt. Xotira O(1).

Muammo: i-elementning "juftini" qidirish uchun qolgan barcha elementlar ko'rilmoqda. Lekin "juft" aniq: target - nums[i]. Agar bu qiymat oldin uchragan bo'lsa, uni bilib olish kerak edi.

Ikkinchi yondashuv: saralayin va ikki ko'rsatkich

Ro'yxatni saralasak, chapdan o'ngga ikkita ko'rsatkich yurishi mumkin:

FUNCTION TWO_SUM_SORTED(nums, target)
    // (index, qiymat) juftlarini saralab
    sorted_pairs = nums ni index bilan birga saralab

    left = 0
    right = n - 1

    WHILE left < right
        current_sum = sorted_pairs[left].qiymat + sorted_pairs[right].qiymat

        IF current_sum = target
            RETURN [sorted_pairs[left].index, sorted_pairs[right].index]

        IF current_sum < target
            left = left + 1
        ELSE
            right = right - 1

    RETURN []

Vaqt: O(n log n) (saralash), xotira: O(n) (index-qiymat juftlari). To'g'ri ishlaydi, lekin asl masala indekslarni so'ragani uchun saralashdan oldin indekslarni saqlash kerak bo'ladi.

Bundan ham tezroq bo'lish mumkin.

Uchinchi yondashuv: hash map

Asosiy fikr: nums[i] uchun kerakli juft target - nums[i] — komplement. Agar bu komplement ilgari ko'rilgan bo'lsa, uning indeksini bilish kerak.

Ro'yxatni bir marta ko'rib chiqamiz. Har nums[i] uchun uning komplementi target - nums[i] allaqachon mapda borligini tekshiramiz. Bor bo'lsa — javob topildi. Yo'q bo'lsa — nums[i]ni uning indeksi bilan mapga qo'shamiz.

FUNCTION TWO_SUM(nums, target)
    seen = bo'sh hash map   // qiymat → indeks

    FOR i = 0 DAN n-1 GACHA
        complement = target - nums[i]

        IF seen CONTAINS complement
            RETURN [seen GET complement, i]

        seen PUT nums[i], i

    RETURN []   // masala shartiga ko'ra bu yerga yetilmaydi

Har element uchun bitta CONTAINS va bitta PUT — ikkisi ham kutiladigan O(1). Jami vaqt O(n). Xotira O(n).

Bosqichma-bosqich dry run

nums = [2, 7, 11, 15], target = 9:

seen = {}

i=0, nums[0]=2
    complement = 9 - 2 = 7
    seen'da 7 bormi? → yo'q
    seen PUT 2 → 0       seen: {2:0}

i=1, nums[1]=7
    complement = 9 - 7 = 2
    seen'da 2 bormi? → HA! indeks = 0
    RETURN [0, 1]

nums = [3, 2, 4], target = 6:

seen = {}

i=0, nums[0]=3
    complement = 6 - 3 = 3
    seen'da 3 bormi? → yo'q
    seen PUT 3 → 0       seen: {3:0}

i=1, nums[1]=2
    complement = 6 - 2 = 4
    seen'da 4 bormi? → yo'q
    seen PUT 2 → 1       seen: {3:0, 2:1}

i=2, nums[2]=4
    complement = 6 - 4 = 2
    seen'da 2 bormi? → HA! indeks = 1
    RETURN [1, 2]

nums = [3, 3], target = 6 — bir xil ikkita element:

seen = {}

i=0, nums[0]=3
    complement = 6 - 3 = 3
    seen'da 3 bormi? → yo'q
    seen PUT 3 → 0       seen: {3:0}

i=1, nums[1]=3
    complement = 6 - 3 = 3
    seen'da 3 bormi? → HA! indeks = 0
    RETURN [0, 1]

Muhim: i=0da birinchi 3 avval mapga qo'yiladi, i=1da esa komplement sifatida topiladi. Bir element ikki marta ishlatilmadi.

Nima uchun PUT dan oldin CONTAINS tekshiriladi?

Agar ketma-ketlik teskari bo'lsa:

nums[i] ni avval qo'ysak:
    i=0, nums[0]=3 → seen PUT 3→0
    complement = 3, seen'da 3 bor → [0, 0] qaytariladi ← xato!

[0, 0] — bir xil indeksni ikki marta ishlatish. Masala "bir elementni ikki marta ishlatib bo'lmaydi" deydi. Shuning uchun avval tekshirish, keyin qo'shish.

Vaqt va xotira murakkabligi

Yondashuv Vaqt Xotira Eslatma
Barcha juftliklar O(n²) O(1) Eng sodda
Saralash + ikki ko'rsatkich O(n log n) O(n) Asl tartib o'zgaradi
Hash map O(n) O(n) Eng tez, tartibni saqlaydi

Hash map yondashuvi eng yaxshi vaqt murakkabligini beradi va asl indekslarni saqlaydi.

Edge case'lar

Bir xil ikkita son. [3, 3], target = 6 — yuqorida ko'rib chiqdik. Avval tekshirish mantiqiga ko'ra to'g'ri ishlaydi.

Manfiy sonlar. [-3, 5, 2], target = -1 — komplement -1 - (-3) = 2. Hash map manfiy kalit uchun alohida tartib talab qilmaydi.

Nol qatnashganda. [0, 4, 3], target = 3 — 0 + 3 = 3. Nol oddiy son sifatida mapga qo'yiladi.

Elementlardan biri nolga teng, target nol. [0, 1, 0], target = 0 — birinchi 0 qo'yiladi, ikkinchi 0 komplement 0ni topadi → [0, 2].

Faqat ikkita element. [5, 5], target = 10 — to'g'ri ishlaydi.

Note

Masala shartiga ko'ra yechim doim mavjud deb taxmin qilinadi. Agar masala "yechim bo'lmasligi mumkin" desa, RETURN [] haqiqatan ham qaytarilishi kerak.

Masalaning variantlari

Indekslar o'rniga qiymatlar. Ba'zan "indekslar" emas, "qiymatlar" qaytarilishi talab qilinadi. Mantiq bir xil, lekin mapda qiymat → indeks o'rniga faqat seen set yetarli bo'lishi mumkin.

Uch son yig'indisi (3Sum). "Yig'indisi nolga teng uchliklar" masalasida saralash + bitta element uchun ikki ko'rsatkich juftlashadi. Hash map ishlatish ham mumkin, lekin takrorlarni boshqarish qiyinlashadi.

Eng ko'p juftliklar soni. Bitta juft emas, hammasi kerak bo'lsa, topilganda RETURN qilish o'rniga natijalar ro'yxatiga qo'shib davom etiladi.

Farq berilgan. "nums[i] - nums[j] = k bo'lgan juft bor-yo'qligini top" — komplement nums[i] - k yoki nums[i] + k bo'lishi mumkin; ikkala holat ham mapda tekshiriladi.

Komplement pattern nima?

Two Sum "komplement" shablonining eng toza namunasi. Bu shablonning mohiyati:

Biror x elementi uchun kerakli "juft" aniq formuladan hisoblanishi mumkin. Agar shu juft avval ko'rilgan bo'lsa — masala yechildi. Ko'rilmagan bo'lsa — xni kelajakdagi elementlar uchun "avval ko'rilgan" sifatida saqlaymiz.

Bir o'tishda hozirgi element ham ko'rilganlar to'plamidan foydalanadi, ham kelajak elementlar uchun qo'shiladi. Bu ro'yxatni bir marta o'qib O(n) da yechish imkonini beradi.

Xulosa

Two Sum hashlashning komplement shablonini ko'rsatadi: target - nums[i] allaqachon ko'rilganmi tekshirish uchun hash map ishlatiladi. O(n²) ikki tsikldan O(n) ga o'tish qo'shimcha O(n) xotira evaziga keladi.

Bir elementni ikki marta ishlatmaslik uchun avval tekshirish, keyin qo'shish muhim. Bu daqiqlik Three Sum, Four Sum va boshqa ko'p yig'indi masalalarida ham saqlanadi.