Ikki ko‘rsatkich va sirpanuvchi oyna: massiv masalalari uchun usullar

Bir daqiqada mohiyat

«Har birini har biri bilan» tekshirish — ikkita ichma-ich sikl va O(n²). Ikkala usul ichki siklni olib tashlaydi:

• Ikki ko‘rsatkich (two pointers) — massiv bo‘ylab bir-biriga qarab yoki bir tomonga turli tezlikda harakatlanadigan ikki indeks.
• Sirpanuvchi oyna (sliding window) — o‘ngdan kengayadigan va chapdan torayadigan uzluksiz [left, right] oralig‘i; kuzatilayotgan qiymat (yig‘indi, belgilar soni) O(1) da yangilanadi.

Asosiy g‘oya: har bir ko‘rsatkich faqat oldinga yuradi va ko‘pi bilan n qadam bosadi, shuning uchun umumiy ish — O(n).

Usulni qanday tanish mumkin

Agar oraliq uzluksiz bo‘lishi shart bo‘lmasa yoki massivda manfiy sonlar bo‘lib, shart yig‘indi haqida bo‘lsa, oyna odatda ishlamaydi — prefiks yig‘indilar yoki hash-jadvallarga qarang.

1-masala. Saralangan massivda berilgan yig‘indili juftlik

To‘liq tanlov barcha juftliklarni tekshiradi — O(n²). Ikki ko‘rsatkich bilan: yig‘indi kichik bo‘lsa, chap ko‘rsatkichni o‘ngga, katta bo‘lsa — o‘ngini chapga suramiz.

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return left, right
        if s < target:
            left += 1
        else:
            right -= 1
    return None

Vaqt O(n), xotira O(1). Bu faqat massiv saralangani uchun ishlaydi: ko‘rsatkichni surish mos kelmaydigan juftliklarni ishonchli tashlab yuboradi.

2-masala. Saralangan massivdan dublikatlarni joyida olib tashlash

Sekin ko‘rsatkich write keyingi noyob element qayerga yozilishini ko‘rsatadi, tez read esa massiv bo‘ylab yuradi.

def dedupe_sorted(nums):
    if not nums:
        return 0
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write  # noyob qism uzunligi

Vaqt O(n), xotira O(1) — yangi ro‘yxat yaratilmaydi.

3-masala. k uzunlikdagi qism-massivning maksimal yig‘indisi

To‘liq tanlov har bir oyna yig‘indisini qaytadan hisoblaydi — O(n·k). Qat’iy o‘lchamli oynada har bir surilishda kirgan elementni qo‘shamiz va chiqqanini ayiramiz.

def max_sum_k(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

Vaqt O(n). 1 <= k <= len(nums) deb faraz qilinadi.

4-masala. Takrorlanuvchi belgilarsiz eng uzun qism-satr

O‘zgaruvchan o‘lchamli oyna: o‘ngdan kengaytiramiz, belgi takrorlansa, chap chegarani uning oldingi uchrashgan joyidan keyinga suramiz.

def longest_unique(s):
    last_seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

Barcha qism-satrlarni noyoblikka tekshirish — O(n²) yoki undan yomon. Bu yerda har bir indeksga bir marta tashrif buyuriladi: O(n) vaqt va alifbo o‘lchamiga mos xotira.

5-masala. Yig‘indisi target dan kam bo‘lmagan eng qisqa qism-massiv

Sonlar musbat. Yig‘indi target dan kichik ekan, oynani kengaytiramiz, so‘ng shart bajarilayotgan ekan, chapdan toraytiramiz va minimal uzunlikni eslab qolamiz.

def min_len_subarray(nums, target):
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

Ichki while yechimni kvadratik qilmaydi: butun o‘tish davomida left ko‘pi bilan n marta suriladi, shuning uchun natija — O(n).

O‘zgaruvchan oyna shabloni

1. right ni massiv bo‘ylab suring va elementni oyna holatiga qo‘shing.
2. Oyna shartni buzayotgan ekan (yoki minimum qidirilganda, aksincha, bajarayotgan ekan), left ni suring va o‘sha elementni holatdan olib tashlang.
3. Har bir qadamdan keyin javobni yangilang.

Ko‘p uchraydigan xatolar

• Manfiy sonli massivda yig‘indi masalalariga oyna qo‘llash — chapdan toraytirish endi yig‘indi kamayishini kafolatlamaydi.
• Bo‘sh massiv va k > len(nums) holatini unutish.
• Oyna uzunligida birga adashish: u right - left + 1 ga teng.
• 4-masalada oldingi uchrashuv joriy oyna ichida ekanini tekshirmaslik.