Sürüşən pəncərə metodu

3.1 Sürüşmə pəncərəsi metodu nədir.

Sürüşmə pəncərəsi metodu (Sliding Window) — bu, massivlər və ya sətirlər üzərində həlli tapmaq üçün istifadə olunan bir üsuldur. Bu üsulda, sabit ölçülü bir alt-massiv (və ya alt-sətir) verilənlərin üzərində hərəkət edir və optimal həlli tapmağa çalışır. Bununla, sabit ölçülü bir pəncərədəki elementlər işlənir və pəncərə dinamik olaraq tapşırığın şərtlərinə uyğun dəyişdirilir.

Bu texnika xüsusilə verilənlər ardıcıllığı ilə bağlı məsələlərdə, məsələn, massivlər və ya sətirlərdə çox faydalıdır və sadə yanaşmalara nisbətən zaman mürəkkəbliyini azaltmağa kömək edir.

Əsas prinsiplər

• Pəncərənin başlanğıcı: Pəncərənin başlanğıc və sonunu ilkin mövqelərə yerləşdirin.
• Pəncərənin sürüşməsi: Pəncərənin sərhədlərini ardıcıl olaraq dəyişdirin, bir tərəfdən elementlər əlavə edin və digər tərəfdən çıxarın.
• Pəncərənin işlənməsi: Hər bir addımda cari pəncərə üçün lazım olan hesablamaları həyata keçirin.

Sürüşmə pəncərəsinin zaman və yaddaş mürəkkəbliyi

Zaman mürəkkəbliyi:

• O(n) — əksər hallarda belədir, çünki göstərici və ya pəncərə massiv boyunca xətti şəkildə hərəkət edir və pəncərənin mümkün olan bütün mövqelərini yoxlayır.

Yaddaş mürəkkəbliyi:

• O(1) — əgər cari dəyərləri saxlamaq üçün sabit miqdarda əlavə yaddaş istifadə olunursa.
• O(k) — əgər cari pəncərənin k ölçülü elementlərini saxlamaq lazım olarsa.

3.2 Alt-massivin maksimum cəminin tapılması.

Fiksasiya olunmuş ölçüyə malik alt-massivin maksimum cəminin tapılması

Problemin təsviri:

Fiksasiya olunmuş ölçüyə malik k alt-massiv tap ki, onun cəmi maksimum olsun.

Həll yolu:

Cari alt-massivin cəmini saxlamaq və pəncərə hərəkət etdikcə maksimum cəmi yeniləmək üçün sürüşən pəncərə metodu istifadə edirik.

Vaxt mürəkkəbliyi: O(n).

Python üçün kod nümunəsi:

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1
            
    window_sum = sum(arr[:k])
    max_sum = window_sum
            
    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
            
    return max_sum
        
        

3.3 Sətirdəki bütün anaqramları tapmaq

Tapşırıq:

Verilmiş p alt sətirinin bütün anaqramlarını s sətirində tapmaq.

Həlli:

Cari pəncərənin simvollarının tezlik lüğətini idarə etmək üçün sürüşən pəncərə metodundan istifadə edirik və bunu alt sətirin tezlik lüğəti ilə müqayisə edirik.

Zaman mürəkkəbliyi: O(n).

Python-da kod nümunəsi:

from collections import Counter

def find_anagrams(s, p):
    p_count = Counter(p)
    s_count = Counter()
                
    result = []
    k = len(p)
                
    for i in range(len(s)):
        s_count[s[i]] += 1
        
        if i >= k:
            if s_count[s[i - k]] == 1:
                del s_count[s[i - k]]
            else:
                s_count[s[i - k]] -= 1
                            
        if s_count == p_count:
            result.append(i - k + 1)

    return result
        

3.4 Minimum alt-massivin tapılması

Verilmiş dəyəri aşan cəmi olan minimum alt-massivin tapılması

Tapşırıq:

Elementlərinin cəmi verilmiş S dəyərini aşan minimum alt-massivi tapmaq.

Həll yolu:

Cəmi S-dən böyük olana qədər sağ sərhədi genişləndirmək üçün sürüşən pəncərə metodundan istifadə edirik, sonra isə sol sərhədi alt-massivin uzunluğunu minimallaşdırmaq üçün irəli çəkirik.

Zaman mürəkkəbliyi: O(n).

Python-da kod nümunəsi:

def min_subarray_len(S, arr):
    n = len(arr)
    min_len = float('inf')
    current_sum = 0
    left = 0
            
    for right in range(n):
        current_sum += arr[right]
                
        while current_sum >= S:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
            
    return 0 if min_len == float('inf') else min_len