Tarkibga o'tish

Texnikalar: two pointers, sliding window, prefix sum

Massiv masalalarini yechishda bir nechta shabloniy yondashuvlar bor. Yangi masalaga duch kelganingizda "buni qanday hal qilsam?" deb noldan fikrlashni boshlasiz. Lekin amalda ko'p masalalar o'xshash tuzilmaga ega — va bir marta bu shablonlarni tanib olsangiz, ularni keyinchalik tez aniqlay olasiz.

Bu qismda uchta kuchli texnikani chuqur ko'rib chiqamiz: ikki ko'rsatkich (two pointers), harakatlanuvchi oyna (sliding window) va oldindan hisoblangan yig'indilar (prefix sum). Ular massiv masalalarida qayta-qayta uchraydigan fundamental usullar.

Ikki ko'rsatkich — two pointers

G'oya

Ko'pgina massiv masalalarida bir vaqtda ikkita joyni kuzatish kerak bo'ladi. Masalan, massivni teskari ko'rinishiga aylantirish uchun boshidan va oxiridan bir vaqtda harakat qilish kerak. Yoki saralangan massivdan ikkita element topish kerak bo'lganda bitta elementi kichikroq, ikkinchisi kattaroq tomonga harakatlansa.

Ikki ko'rsatkich texnikasida massivda ayni vaqtda ikkita index saqlanadi. Ular muammoning mantiqiga qarab harakatlanadi. Bu ko'pincha ichma-ich ikkita takrorlash o'rniga bitta takrorlashda yechimga yetishga yordam beradi — O(n²) o'rniga O(n).

Ikki ko'rsatkichning asosan ikkita ko'rinishi bor:

  1. Qarama-qarshi uchlardan — biri boshdan, biri oxirdan;
  2. Bir yo'nalishda — ikkalasi ham boshdan, lekin har xil tezlikda.

Ko'rinish 1: qarama-qarshi uchlardan

Bu ko'rinishda biri 0-indexdan, ikkinchisi n-1-indexdan boshlab bir-biriga qarab harakatlanadi. Ular uchrashganda to'xtaydi.

Massivni joyida teskari aylantirish:

FUNCTION teskari_aylantir(array)
    chap = 0
    o'ng = array uzunligi - 1

    WHILE chap < o'ng
        array[chap] VA array[o'ng] JOYINI ALMASHTIR
        chap = chap + 1
        o'ng = o'ng - 1

Boshlang'ich: [1, 2, 3, 4, 5]
               ↑           ↑
              chap        o'ng

1-qadam: 1 va 5 almashtirildi → [5, 2, 3, 4, 1]
               chap ↑   ↑ o'ng

2-qadam: 2 va 4 almashtirildi → [5, 4, 3, 2, 1]
                   ↑
               chap = o'ng, to'xtaymiz

Bu O(n) vaqt va O(1) xotira. Qo'shimcha massiv kerak emas.

Palindromni tekshirish:

Satr (yoki massiv) palindrommi? Boshdan va oxirdan bir vaqtda kelib, mos elementlarni taqqoslaydi.

FUNCTION palindrommi(array)
    chap = 0
    o'ng = array uzunligi - 1

    WHILE chap < o'ng
        IF array[chap] ≠ array[o'ng]
            RETURN FALSE
        chap = chap + 1
        o'ng = o'ng - 1

    RETURN TRUE

"racecar" uchun:
r . . a . . r     → mos ✓
  a . . . a       → mos ✓
    c . c         → mos ✓
      e           → o'rta, to'xtaymiz → TRUE

Saralangan massivdan yig'indisi berilgan ikkita sonni topish:

FUNCTION ikki_son_yigindisi(array, maqsad)
    chap = 0
    o'ng = array uzunligi - 1

    WHILE chap < o'ng
        yigindi = array[chap] + array[o'ng]

        IF yigindi = maqsad
            RETURN (chap, o'ng)
        ELSE IF yigindi < maqsad
            chap = chap + 1
        ELSE
            o'ng = o'ng - 1

    RETURN topilmadi

Nima uchun bu ishlaydi? Massiv saralangan. Agar yig'indi maqsaddan kichik bo'lsa, kattaroq qiymat kerak — chap o'ngga suriladi. Agar yig'indi maqsaddan katta bo'lsa, kichikroq qiymat kerak — o'ng chapga suriladi. Har qadam birdaniga bir imkoniyatni yo'q qiladi.

[2, 7, 11, 15], maqsad = 9

chap=0, o'ng=3: 2 + 15 = 17 > 9 → o'ng--
chap=0, o'ng=2: 2 + 11 = 13 > 9 → o'ng--
chap=0, o'ng=1: 2 + 7 = 9 = maqsad → (0, 1) ✓

Ko'rinish 2: bir yo'nalishda (sekin va tez ko'rsatkich)

Bu ko'rinishda ikki ko'rsatkich ham boshdan harakat qiladi, lekin biri sekin, ikkinchisi tez. Ular bir-birlarining orasidagi oraliq yoki munosabatiga qarab ishlaydi.

Massivdan nollarni tashlab, tartibni saqlagan holda siqish:

Agar masalaga saralangan massiv sharti yo'q bo'lsa ham ikki ko'rsatkich yordam beradi. Siz nollarni olib, qolgan elementlarni old tomonga yig'moqchisiz:

FUNCTION nollarni_siqish(array)
    yozish_joyi = 0

    FOR o'qish = 0 DAN array uzunligi - 1 GACHA
        IF array[o'qish] ≠ 0
            array[yozish_joyi] = array[o'qish]
            yozish_joyi = yozish_joyi + 1

    WHILE yozish_joyi < array uzunligi
        array[yozish_joyi] = 0
        yozish_joyi = yozish_joyi + 1

[0, 1, 0, 3, 12]
 ↑              o'qish
 ↑              yozish_joyi

0 = 0 → o'tkazib yuborildi. o'qish olg'a.
1 ≠ 0 → yozish_joyiga yozildi: [1, 1, 0, 3, 12], yozish_joyi++
0 = 0 → o'tkazib yuborildi.
3 ≠ 0 → yozildi: [1, 3, 0, 3, 12], yozish_joyi++
12 ≠ 0 → yozildi: [1, 3, 12, 3, 12], yozish_joyi++

Qolgan joyga nol: [1, 3, 12, 0, 0] ✓

Takroriy elementlarni olib tashlash (saralangan massivda):

FUNCTION takrorlarni_olt(array)
    IF array uzunligi = 0
        RETURN 0

    yozish_joyi = 1

    FOR o'qish = 1 DAN array uzunligi - 1 GACHA
        IF array[o'qish] ≠ array[o'qish - 1]
            array[yozish_joyi] = array[o'qish]
            yozish_joyi = yozish_joyi + 1

    RETURN yozish_joyi

[1, 1, 2, 3, 3, 4]

o'qish=1: 1 = 1 → o'tkazib yuborildi
o'qish=2: 2 ≠ 1 → yozildi: [1, 2, 2, 3, 3, 4], yozish_joyi=2
o'qish=3: 3 ≠ 2 → yozildi: [1, 2, 3, 3, 3, 4], yozish_joyi=3
o'qish=4: 3 = 3 → o'tkazib yuborildi
o'qish=5: 4 ≠ 3 → yozildi: [1, 2, 3, 4, 3, 4], yozish_joyi=4

Natija: birinchi 4 ta element → [1, 2, 3, 4]

Qachon ikki ko'rsatkich ishlatish kerak?

  • Saralangan massivda ikkita elementning yig'indisi, farqi yoki ko'paytmasi bo'yicha qidirish;
  • Massivni joyida o'zgartirish (teskari aylantirish, siqish, takrorlarni olib tashlash);
  • Muammo "ikkita indeksni boshqarish" shaklida ko'ringanda.

Agar muammo "bir vaqtda ikkita joyga nazar tashlash" talabi bilan kelsa — ikki ko'rsatkich ehtimol to'g'ri yo'l.

Harakatlanuvchi oyna — sliding window

G'oya

Massivning ketma-ket kelgan bir nechta elementlari ustida hisoblash kerak bo'lganda — masalan, har 5 ta kunning o'rtacha harorati, yoki uzunligi k bo'lgan bo'lakdagi eng katta yig'indi — to'g'ridan-to'g'ri yondashuv har bo'lak uchun qaytadan hisoblash talab qiladi.

Masalan, [5, 2, 7, 4, 6] massivida har 3 ta elementning yig'indisi:

[5, 2, 7] → 14
   [2, 7, 4] → 13
      [7, 4, 6] → 17

Naiv yondashuv: har bo'lak uchun k ta element qo'shiladi. Agar massivda n ta element bo'lsa, bu O(n × k) bo'ladi.

Aqlliroq yol: oynani bir katak o'ngga surayotganda, faqat bitta yangi element qo'shiladi va bitta eski element ayiriladi. Avvalgi hisob qaytadan bajarilmaydi.

[5, 2, 7] → yig'indi = 14
    + 4       yangi element
  - 5         chiqib ketgan element
   [2, 7, 4] → 14 + 4 - 5 = 13 ✓

Bu sliding window — "harakatlanuvchi oyna". Oyna massiv ustida bitta katak o'ngga surilib boradi. Har surishda faqat ikki ta arifmetik amal: bir qo'shish va bir ayirish.

Ko'rinish 1: belgilangan o'lchamli oyna (fixed size)

Oyna o'lchami k oldindan ma'lum va o'zgarmaydi.

Uzunligi k bo'lgan bo'lakning eng katta yig'indisi:

FUNCTION eng_katta_yigindi_k(array, k)
    n = array uzunligi
    IF n < k
        RETURN XATO

    joriy_yigindi = 0
    FOR i = 0 DAN k - 1 GACHA
        joriy_yigindi = joriy_yigindi + array[i]

    eng_katta = joriy_yigindi

    FOR i = k DAN n - 1 GACHA
        joriy_yigindi = joriy_yigindi + array[i] - array[i - k]
        IF joriy_yigindi > eng_katta
            eng_katta = joriy_yigindi

    RETURN eng_katta

array = [2, 1, 5, 1, 3, 2], k = 3

1-oyna: 2 + 1 + 5 = 8
2-oyna: 8 + 1 - 2 = 7   (array[3] qo'sh, array[0] olib tashla)
3-oyna: 7 + 3 - 1 = 9
4-oyna: 9 + 2 - 5 = 6

eng_katta = 9 ✓

Murakkablik: O(n) vaqt, O(1) xotira. Naiv yondashuv O(n × k) bo'lardi.

Ko'rinish 2: o'zgaruvchan o'lchamli oyna (variable size)

Oyna o'lchami aniq emas — u muammo shartiga qarab kattalashadi yoki kichiklashadi.

Yig'indisi maqsaddan katta bo'lgan eng qisqa bo'lak:

FUNCTION eng_qisqa_bolak(array, maqsad)
    chap = 0
    joriy_yigindi = 0
    eng_qisqa = CHEKSIZ

    FOR o'ng = 0 DAN array uzunligi - 1 GACHA
        joriy_yigindi = joriy_yigindi + array[o'ng]

        WHILE joriy_yigindi >= maqsad
            uzunlik = o'ng - chap + 1
            IF uzunlik < eng_qisqa
                eng_qisqa = uzunlik
            joriy_yigindi = joriy_yigindi - array[chap]
            chap = chap + 1

    IF eng_qisqa = CHEKSIZ
        RETURN 0
    RETURN eng_qisqa

array = [2, 3, 1, 2, 4, 3], maqsad = 7

o'ng=0: yig'indi=2
o'ng=1: yig'indi=5
o'ng=2: yig'indi=6
o'ng=3: yig'indi=8 >= 7 → uzunlik=4, chap+1: yig'indi=6
o'ng=4: yig'indi=10 >= 7 → uzunlik=4, chap+1: yig'indi=7 >= 7 → uzunlik=3, chap+1: yig'indi=4
o'ng=5: yig'indi=7 >= 7 → uzunlik=2, chap+1: yig'indi=3

eng_qisqa = 2 ([4, 3]) ✓

Bu yondashuv O(n) da ishlaydi. chap va o'ng har biri massiv bo'ylab ko'pi bilan n marta siljiydi — jami O(2n) = O(n).

Sliding window uchun umumiy shablon

chap = 0
joriy_holat = bo'sh/nol

FOR o'ng = 0 DAN n - 1 GACHA
    joriy_holatga array[o'ng] QO'SH

    WHILE shart bajarilmayaptimi yoki o'lcham kattalashdi
        joriy_holatdan array[chap] OLIB TASHLA
        chap = chap + 1

    NATIJANI YANGILASHTIR

Ushbu shablon ko'p variantda qo'llaniladi — qo'shiladigan va olinadigan qiymat sonlar, belgilar, tezlik yoki boshqa ko'rinishda bo'lishi mumkin.

Qachon sliding window ishlatish kerak?

  • Ketma-ket elementlar bo'laklari bilan ishlash kerak bo'lganda;
  • "Belgilangan o'lchamli oyna ichida ..." yoki "eng qisqa/uzun bo'lak ..." shaklidagi masalalarda;
  • Ichma-ich ikkita takrorlash O(n²) dan O(n) ga tushirilishi kerak bo'lganda.

Agar "ketma-ket elementlar" so'zi masalada kelsa yoki "subarray" (qism massiv) bilan ishlash kerak bo'lsa — sliding window ko'p hollarda to'g'ri yo'l.

Oldindan hisoblangan yig'indilar — prefix sum

G'oya

Tez-tez bir xil massivning turli oralig'idagi yig'indi so'ralsa, har safar o'sha oraliq bo'ylab yurish O(n) vaqt oladi. Ko'p so'rov bo'lsa, bu qimmatga tushadi.

Prefix sum (oldindan hisoblangan yig'indilar) yondashuvi bir marta O(n) da barcha "boshlang'ichdan u gacha" yig'indilarini hisoblab, massivda saqlaydi. Keyin istalgan [i, j] oralig'i yig'indisi O(1) da topiladi.

Bu "bir marta hisob, ko'p marta foydalanish" g'oyasi.

Prefix massivini qurish

Asl massiv: [3, 5, 2, 4, 1]

prefix[i] — asl massivning 0-indexdan i-indexgacha (shu index ham kirib) bo'lgan elementlar yig'indisi.

Asl:    [ 3,  5,  2,  4,  1]
Index:    0   1   2   3   4

prefix[0] = 3
prefix[1] = 3 + 5 = 8
prefix[2] = 3 + 5 + 2 = 10
prefix[3] = 3 + 5 + 2 + 4 = 14
prefix[4] = 3 + 5 + 2 + 4 + 1 = 15

Prefix: [ 3,  8, 10, 14, 15]

FUNCTION prefix_qur(array)
    n = array uzunligi
    prefix = n o'lchamli yangi massiv

    prefix[0] = array[0]

    FOR i = 1 DAN n - 1 GACHA
        prefix[i] = prefix[i - 1] + array[i]

    RETURN prefix

Oraliq yig'indisini so'rash

[i, j] oralig'i yig'indisi quyidagi formula bilan:

FUNCTION oraliq_yigindi(prefix, i, j)
    IF i = 0
        RETURN prefix[j]
    RETURN prefix[j] - prefix[i - 1]

Nima uchun? prefix[j] — 0-dan j-gacha yig'indi. prefix[i-1] — 0-dan i-1-gacha yig'indi. Ikkinchisini birinchisidan ayirsak, i-dan j-gacha bo'lgan yig'indi qoladi.

Asl:    [3, 5, 2, 4, 1]
Prefix: [3, 8, 10, 14, 15]

[1, 3] oralig'i yig'indisi — ya'ni 5 + 2 + 4 = 11:
prefix[3] - prefix[0] = 14 - 3 = 11 ✓

[2, 4] oralig'i yig'indisi — ya'ni 2 + 4 + 1 = 7:
prefix[4] - prefix[1] = 15 - 8 = 7 ✓

Amaliy misol: kunlik savdo hisobotlari

Server qaysi kunlardan qaysi kunlargacha savdo hajmini qaytarishi kerak. Savdo hajmlari massivda: [120, 340, 210, 450, 180, 270, 390].

Prefix summasi quriladi — bir marta. Keyin istalgan oraliq uchun savdo hajmi O(1) da hisob-kitob qilinadi. Agar bu so'rov ko'p bo'lsa — kuniga minglab hisobot — prefix sum katta tejamkorlik beradi.

Ikki o'lchamli prefix sum

Ikki o'lchamli massivda ham prefix sum ishlatiladi — masalan, rasmdagi to'rtburchak hududning piksel yig'indisini tez topish uchun.

Ikki o'lchamli prefix:

prefix[i][j] = 0-dan i-gacha, 0-dan j-gacha bo'lgan qismning yig'indisi

Qurilishi:

prefix[i][j] = array[i][j]
             + prefix[i-1][j]
             + prefix[i][j-1]
             - prefix[i-1][j-1]

Oxirgi ayirish sababi: prefix[i-1][j] va prefix[i][j-1] birgalikda prefix[i-1][j-1] ni ikki marta hisoblaydi — shu sababli bir marta ayiriladi.

Bu rasmni qayta ishlash, mozaika yoki to'r formatidagi ma'lumotlarda foydali.

Murakkablik

Bosqich Vaqt Xotira
Prefix massivini qurish O(n) O(n)
Bitta oraliq so'rovi O(1) —
q ta so'rov O(n + q) O(n)

Prefix sum O(n) oldingi hisob bilan har bir so'rovni O(1) ga tushiradi. Agar q ta so'rov bo'lsa va q katta bo'lsa, bu O(n × q) naiv yondashuvga qaraganda ancha tezroq.

Qachon prefix sum ishlatish kerak?

  • Bir xil massivda ko'p marta oraliq yig'indisi so'ralganda;
  • "Ushbu oraliqda nechta element shartni qanoatlantiradi?" shaklidagi masalalarda;
  • Ikki o'lchamli massivda to'rtburchak hududlar bilan ishlashda.

Prefix sum yordamida oraliq yig'indisi so'rovlari O(n) dan O(1) ga tushiriladi — oldindan O(n) xarajat evaziga.

Uchala texnikani qiyosiy ko'rish

Texnika Asosiy g'oya Klassik muammo Vaqt
Two pointers Ikkita joyni bir vaqtda kuzatish Yig'indisi X bo'lgan ikki son O(n)
Sliding window Oyna surilib boradi, qaytadan hisob yo'q Uzunligi k bo'lgan eng katta bo'lak O(n)
Prefix sum Oldindan hisoblab, tez so'rash Ko'p oraliq yig'indisi so'rovi O(n + q)

Keng tarqalgan xatolar

Sliding windowda chapni surishni unutish

Oyna o'lchamini nazorat qilmasdan faqat o'ng ko'rsatkichni harakatlatish — oyna cheksiz kattalashib ketadi va noto'g'ri natija beradi. chap ko'rsatkichi belgilangan qoidaga muvofiq siljishi kerak.

Prefix sumda i = 0 holati

prefix[j] - prefix[i-1] formulasida i = 0 bo'lsa, prefix[-1] ga murojaat qilinadi — bu mavjud emas. Shu sababli i = 0 holati alohida ko'rib chiqilishi kerak: prefix[j] ni qaytarish yetarli.

Two pointersda cheksiz loop

chap va o'ng ko'rsatkichlari har qadam siljishi kerak — aks holda algoritm bir joyda aylanib qoladi. WHILE sikli shartiga qarab kamida bittasi siljishi kafolatlanishi kerak.

Naiv yondashuv bilan boshlash

Sliding window yoki two pointers zarur bo'lgan masalada to'g'ridan-to'g'ri ichma-ich ikkita takrorlash yozish O(n²) ga olib keladi. Agar masalada "ketma-ket elementlar" yoki "ikkita ko'rsatkich bo'yicha qidiruv" ko'rinsa, avval bu texnikalarni ko'rib chiqish kerak.

Qachon bu texnikalarni qo'llash kerak?

Two pointers: - Massiv saralangan va ikkita element o'rtasidagi munosabat kerak bo'lsa; - Massivni joyida o'zgartirish, siqish, ayirish kerak bo'lsa; - "Boshidan va oxiridan yuring" yoki "sekin va tez yuring" mantiqida masala bo'lsa.

Sliding window: - "Uzunligi k bo'lgan bo'lak", "eng qisqa bo'lak, shartni qanoatlantiruvchi" kabi masalalar; - Ketma-ket elementlar oralig'i bilan ishlash; - Har bo'lak uchun qaytadan hisob keraksiz bo'lganda.

Prefix sum: - Bir massivda ko'p marta oraliq yig'indisi so'ralsa; - Hisoblash oldindan bajarilishi mumkin bo'lsa (massiv o'zgarmasa yoki kamdan-kam o'zgarse); - Ikki o'lchamli masalalar uchun ham prefix sum varianti bor.

Eng muhim xulosa

Uchala texnika ham bitta umumiy g'oyani turli shakllarda amalga oshiradi: avvalgi hisob natijasidan foydalanib, qaytadan ish qilmaslik. Buni "ortiqcha ishni yo'qotish" deb tasavvur qilish mumkin.

  • Two pointers: bir vaqtda ikkita joyni kuzatib, taqqoslash sonini kamaytiradi.
  • Sliding window: oynadagi o'zgarishni inkremental hisoblaydi, butun oynani qaytadan hisob qilmaydi.
  • Prefix sum: yig'indilarni oldindan hisoblaydi, har so'rov uchun faqat ikki ta amal bajaradi.

Bu shablonlarni bilish massiv masalalarini ko'rganda "bu qanday ko'rinadi?" deb tezroq tanib olishga yordam beradi. Keyingi qismda ushbu texnikalarni amalda ishlatadigan klassik masalalarni ko'ramiz.

📍 Toshkent, O'zbekiston
🗓️
👤