Phương pháp cửa sổ trượt

3.1 Định nghĩa phương pháp cửa sổ trượt.

Phương pháp cửa sổ trượt (Sliding Window) — là một kỹ thuật dùng để giải các bài toán về mảng hoặc chuỗi, trong đó một mảng con cố định (hoặc chuỗi con) được di chuyển qua dữ liệu để tìm kiếm giải pháp tối ưu. Điều này cho phép xử lý các phần tử trong một cửa sổ có kích thước cố định và thay đổi kích thước cửa sổ dựa trên điều kiện của nhiệm vụ.

Kỹ thuật này đặc biệt hữu ích cho các bài toán liên quan đến chuỗi dữ liệu, như mảng hoặc chuỗi, và giúp giảm độ phức tạp thời gian so với các cách tiếp cận ngây thơ hơn.

Các nguyên tắc chủ yếu

• Khởi tạo cửa sổ: Đặt điểm đầu và điểm cuối của cửa sổ tại vị trí ban đầu.
• Di chuyển cửa sổ: Liên tục di chuyển các biên của cửa sổ, thêm phần tử từ một bên và loại bỏ phần tử ở bên kia.
• Xử lý cửa sổ: Tại mỗi bước, thực hiện các tính toán cần thiết cho cửa sổ hiện tại.

Độ phức tạp thời gian và không gian của phương pháp cửa sổ trượt

Độ phức tạp thời gian:

• O(n) — trong hầu hết các trường hợp, bởi vì con trỏ hoặc cửa sổ di chuyển tuyến tính qua mảng, kiểm tra mỗi vị trí có thể của cửa sổ.

Độ phức tạp không gian:

• O(1) — nếu sử dụng số lượng cố định bộ nhớ bổ sung để lưu trữ các giá trị hiện tại.
• O(k) — nếu cần lưu trữ các phần tử bên trong cửa sổ hiện tại có kích thước k.

3.2 Tìm tổng lớn nhất của mảng con.

Tìm tổng lớn nhất của mảng con có kích thước cố định

Bài toán:

Tìm mảng con có kích thước cố định k với tổng lớn nhất.

Giải pháp:

Sử dụng phương pháp cửa sổ trượt để duy trì tổng hiện tại của mảng con và cập nhật tổng lớn nhất khi cửa sổ di chuyển.

Độ phức tạp thời gian: O(n).

Ví dụ mã Python:

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 Tìm tất cả các anagram của chuỗi con trong chuỗi

Bài toán:

Tìm tất cả các anagram của chuỗi con đã cho p trong chuỗi s.

Giải pháp:

Sử dụng phương pháp cửa sổ trượt để duy trì từ điển tần suất các ký tự của cửa sổ hiện tại và so sánh nó với từ điển tần suất của chuỗi con.

Độ phức tạp thời gian: O(n).

Ví dụ mã Python:

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 Tìm mảng con tối thiểu

Tìm mảng con có tổng lớn hơn giá trị đã cho

Bài toán:

Tìm mảng con tối thiểu có tổng các phần tử lớn hơn giá trị đã cho S.

Giải pháp:

Sử dụng phương pháp cửa sổ trượt để mở rộng biên phải cho đến khi tổng lớn hơn S, sau đó di chuyển biên trái để tối thiểu hóa độ dài của mảng con.

Độ phức tạp thời gian: O(n).

Ví dụ mã Python:

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