Kỹ thuật sliding window là gì?

Question

Accepted Answer

Kỹ thuật **sliding window** duy trì một phạm vi liên tục (cửa sổ) trên một mảng hoặc chuỗi và trượt nó thay vì tính lại từ đầu, giải nhiều bài toán mảng con/chuỗi con trong **O(n)**.

## Ý tưởng

Mở rộng cửa sổ bằng cách dịch cạnh phải; thu hẹp nó bằng cách dịch cạnh trái khi một ràng buộc bị vi phạm. Tái sử dụng phép tính trước đó thay vì quét lại.

## Ví dụ: tổng lớn nhất của cửa sổ kích thước k bất kỳ

```python
def max_window_sum(arr, k):
    window = sum(arr[:k])       # tổng của cửa sổ đầu tiên
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # thêm phần tử mới, bỏ phần tử cũ
        best = max(best, window)
    return best

max_window_sum([2, 1, 5, 1, 3, 2], 3)  # -> 9 (5+1+3)
```

## Độ phức tạp

- **Thời gian:** O(n) — mỗi phần tử vào và ra khỏi cửa sổ đúng một lần.
- **Bộ nhớ:** O(1) cho cửa sổ cố định, O(k) khi cần theo dõi nội dung.

## Khi nào dùng / những cạm bẫy

Dùng cho các bài toán "mảng con dài nhất/ngắn nhất/lớn nhất có tính chất X". Với cửa sổ **biến đổi**, dịch con trỏ trái để khôi phục ràng buộc. Cẩn thận lỗi sai-một-đơn-vị khi thêm/bớt các phần tử ở biên.

## Tại sao điều này quan trọng

Sliding window loại bỏ công việc dư thừa, biến phép tính lại O(n·k) thành một lần duyệt.

Đây là mô thức ưu tiên cho các bài toán chuỗi con và mảng con xuất hiện thường xuyên trong phỏng vấn.

Kiến giải cốt lõi — tái sử dụng kết quả trước thay vì tính lại — khái quát hóa được cho dữ liệu streaming và thời gian thực.