Kỹ thuật cửa sổ trượt (Sliding Window): cố định, co giãn, code C++ và Python

Ý tưởng cửa sổ trượt qua hình ảnh khung kính trượt trên băng chuyền

Giả sử bạn có mảng a = [2, 1, 5, 1, 3, 2] và cần tìm tổng lớn nhất của 3 phần tử đứng liên tiếp nhau (k = 3).

Nếu làm theo cách ngây thơ, tại mỗi vị trí bắt đầu bạn lại cộng 3 phần tử từ đầu:

• Đoạn 1: 2 + 1 + 5 = 8
• Đoạn 2: 1 + 5 + 1 = 7
• Đoạn 3: 5 + 1 + 3 = 9
• Đoạn 4: 1 + 3 + 2 = 6

Hãy để ý chuyển động từ Đoạn 1 [2, 1, 5] sang Đoạn 2 [1, 5, 1]: hai số ở giữa là 1 và 5 vẫn nằm nguyên trong khung! Thay vì cộng lại cả k phần tử (rất chậm nếu k = 50.000), ta chỉ cần lấy tổng cũ trừ đi phần tử vừa bị đẩy ra ở bên trái (2) và cộng thêm phần tử mới vừa bước vào ở bên phải (1).

Dạng 1: Cửa sổ trượt có kích thước cố định K

Khi đề bài cho trước độ dài cố định k của đoạn con liên tiếp, thuật toán luôn gồm 2 bước rõ ràng:

1. Khởi tạo cửa sổ đầu tiên: Tính tổng (hoặc số lượng phần tử thỏa điều kiện) của cửa sổ đầu tiên gồm đúng k phần tử từ vị trí 0 đến k - 1. Ghi nhận giá trị này làm kỷ lục ban đầu best = cur.
2. Trượt từng bước sang phải: Cho chỉ số đầu phải i trượt từ k đến n - 1. Tại mỗi bước, phần tử mới bước vào cửa sổ ở biên phải là a[i], còn phần tử vừa tụt lại phía sau biên trái của cửa sổ là a[i - k]. Công thức cập nhật chỉ mất đúng hai phép toán số học: cur += a[i] - a[i - k]

Hãy đối chiếu chi tiết từng chỉ số khi k = 3 trên mảng a = [2, 1, 5, 1, 3, 2] để không bao giờ nhầm biên trái i - k:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// Tìm tổng lớn nhất của đoạn con liên tiếp có độ dài đúng k
long long tongDoanDaiK(const vector<int>& a, int k) {
    long long cur = 0;
    for (int i = 0; i < k; ++i) {
        cur += a[i];  // tổng cửa sổ đầu tiên [0 .. k-1]
    }
    long long best = cur;
    for (int i = k; i < (int)a.size(); ++i) {
        cur += a[i] - a[i - k];  // thêm phần tử mới bên phải, bớt phần tử cũ bên trái
        best = max(best, cur);
    }
    return best;
}

int main() {
    vector<int> a = {2, 1, 5, 1, 3, 2};
    cout << tongDoanDaiK(a, 3) << "\n";  // 9 (đoạn [5, 1, 3])
    return 0;
}

def tong_doan_dai_k(a, k):
    """Tìm tổng lớn nhất của đoạn con liên tiếp có độ dài đúng k."""
    cur = sum(a[:k])
    best = cur
    for i in range(k, len(a)):
        cur += a[i] - a[i - k]  # thêm phải, bớt trái
        if cur > best:
            best = cur
    return best


a = [2, 1, 5, 1, 3, 2]
print(tong_doan_dai_k(a, 3))  # 9

Cách này chỉ cần một vòng lặp duy nhất đi qua mảng trong thời gian O(n) và bộ nhớ phụ O(1), bất kể k lớn tới đâu. Nếu n = 1.000.000 và k = 500.000, cách cộng lại từ đầu mất khoảng 2,5 × 10¹¹ phép tính (quá thời gian hàng trăm giây), trong khi cửa sổ trượt chỉ làm đúng 1.000.000 phép cộng trừ và chạy xong trong vài mili-giây.

Ngoài bài toán tính tổng đoạn dài k, mẫu cửa sổ cố định còn áp dụng trực tiếp cho rất nhiều câu hỏi thực tế khác:

• Trung bình cộng lớn nhất của đoạn dài k: tìm tổng lớn nhất của cửa sổ dài k rồi chia cho k ở bước cuối cùng.
• Đoạn dài k chứa nhiều số chẵn (hoặc nguyên âm) nhất: thay vì cộng giá trị a[i], ta cộng 1 nếu a[i] thỏa điều kiện và trừ 1 nếu a[i - k] thỏa điều kiện.
• Kiểm tra xem có đoạn con độ dài k nào có tổng đúng bằng S hay không: chỉ cần kiểm tra if (cur == S) ngay sau mỗi bước trượt.

Dạng 2: Cửa sổ trượt có kích thước thay đổi (Co giãn)

Trong nhiều bài toán thực tế, độ dài cửa sổ không cố định mà chính là thứ đề bài yêu cầu tìm. Ví dụ kinh điển: "Cho mảng các số nguyên dương a = [3, 1, 2, 7, 4, 2, 1, 1, 5] và số S = 8. Tìm độ dài của đoạn con liên tiếp dài nhất có tổng không vượt quá 8."

Lúc này ta kết hợp kỹ thuật hai con trỏ cùng chiều l (biên trái) và r (biên phải) như một con sâu đo co giãn trên mảng:

1. Mở rộng biên phải r: Vòng lặp ngoài cho r nhích từng bước từ 0 đến n - 1, cộng a[r] vào trạng thái của cửa sổ hiện tại cur (kéo giãn đầu phải của cửa sổ thêm 1 ô).
2. Thu hẹp biên trái l khi vi phạm điều kiện: Ngay sau khi thêm a[r], nếu tổng cur > S (cửa sổ bị quá tải), ta dùng vòng lặp while (cur > S) để trừ bớt a[l] và tăng l++ (rút ngắn đuôi trái lại) cho tới khi cur <= S trở lại.
3. Cập nhật đáp án khi cửa sổ hợp lệ: Khi vòng while kết thúc, cửa sổ [l..r] chắc chắn là cửa sổ hợp lệ dài nhất kết thúc tại vị trí r. Độ dài của nó là r - l + 1, và ta cập nhật kết quả tốt nhất best = max(best, r - l + 1).

Hãy xem bảng chạy từng bước với a = [3, 1, 2, 7, 4, 2, 1, 1, 5] và S = 8:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// Tìm độ dài đoạn con liên tiếp dài nhất có tổng <= S (với mảng số nguyên dương)
int doanDaiNhatTongNhoHonS(const vector<int>& a, long long S) {
    int l = 0, best = 0;
    long long cur = 0;
    for (int r = 0; r < (int)a.size(); ++r) {
        cur += a[r];                 // mở rộng biên phải của cửa sổ
        while (cur > S) {            // khi tổng vượt quá S thì thu hẹp biên trái
            cur -= a[l];
            l++;
        }
        best = max(best, r - l + 1); // cửa sổ [l..r] hiện tại hợp lệ
    }
    return best;
}

int main() {
    vector<int> a = {3, 1, 2, 7, 4, 2, 1, 1, 5};
    cout << doanDaiNhatTongNhoHonS(a, 8) << "\n";  // 4 (đoạn [4, 2, 1, 1])
    return 0;
}

def doan_dai_nhat_tong_nho_hon_s(a, s):
    """Tìm độ dài đoạn con liên tiếp dài nhất có tổng <= s (mảng dương)."""
    l = 0
    cur = 0
    best = 0
    for r, val in enumerate(a):
        cur += val          # mở rộng biên phải
        while cur > s:      # thu hẹp biên trái khi tổng vượt quá s
            cur -= a[l]
            l += 1
        if r - l + 1 > best:
            best = r - l + 1
    return best


a = [3, 1, 2, 7, 4, 2, 1, 1, 5]
print(doan_dai_nhat_tong_nho_hon_s(a, 8))  # 4

Ba biến thể cửa sổ co giãn hay gặp nhất trong đề thi

Cùng một khung for (r) kết hợp while (l), chỉ cần thay đổi vị trí cập nhật đáp án là bạn giải quyết được 3 bài toán hoàn toàn khác nhau:

1. Tìm đoạn con DÀI NHẤT thỏa mãn điều kiện (ví dụ: tổng ≤ S)

• Khi nào thu hẹp l: Trong vòng while, chừng nào cửa sổ đang vi phạm điều kiện (cur > S) thì tăng l++.
• Khi nào cập nhật best: Đặt câu lệnh best = max(best, r - l + 1) ở bên ngoài, ngay phía sau vòng while, vì lúc đó cửa sổ [l..r] đã quay trở lại trạng thái hợp lệ.

2. Tìm đoạn con NGẮN NHẤT đạt ngưỡng yêu cầu (ví dụ: tổng ≥ S)

• Khi nào thu hẹp l: Trong vòng while, chừng nào cửa sổ đã đạt yêu cầu (cur >= S), ta thử ép nhỏ nó lại xem có ngắn hơn được nữa không.
• Khi nào cập nhật best: Đặt câu lệnh best = min(best, r - l + 1) ngay bên trong vòng while, trước dòng trừ a[l] và tăng l++. Lý do là chỉ khi đang ở bên trong vòng while (cur >= S) thì cửa sổ mới thỏa mãn điều kiện >= S; ngay khi thoát khỏi while thì tổng đã tụt xuống < S rồi!

3. Đếm số lượng đoạn con liên tiếp thỏa mãn điều kiện (ví dụ: đếm số đoạn có tổng ≤ S)

• Sau khi vòng while (cur > S) kết thúc, nếu cả đoạn lớn [l..r] có tổng ≤ S (với mảng toàn số dương), thì mọi đoạn con kết thúc tại r và bắt đầu tại một vị trí bất kỳ từ l đến r ([l..r], [l+1..r], ..., [r..r]) cũng đều có tổng ≤ S.
• Có đúng r - l + 1 đoạn con như vậy kết thúc tại r. Do đó ở mỗi bước r, ta chỉ cần cộng dồn count += (r - l + 1) là đếm được toàn bộ số đoạn con hợp lệ trên mảng chỉ trong O(n)!

Cửa sổ trượt trên xâu ký tự và mảng tần suất

Không chỉ áp dụng cho tổng số học, cửa sổ trượt co giãn còn là công cụ số một để xử lý xâu ký tự (string) và các bài toán đếm số phần tử phân biệt. Thay vì biến cur lưu tổng, trạng thái của cửa sổ [l..r] lúc này là một mảng đếm tần suất cnt (kích thước 256 cho bảng mã ASCII hoặc bảng băm) cùng biến distinct đếm số loại ký tự khác nhau đang có mặt trong cửa sổ:

• Khi mở rộng biên phải r (thêm ký tự s[r]): nếu cnt[s[r]] == 0 (ký tự này chưa từng xuất hiện trong cửa sổ hiện tại), ta tăng distinct++. Sau đó tăng cnt[s[r]]++.
• Khi thu hẹp biên trái l (bớt ký tự s[l]): ta giảm cnt[s[l]]--. Nếu sau khi giảm mà cnt[s[l]] == 0 (ký tự này đã rút hết khỏi cửa sổ), ta giảm distinct--. Sau đó tăng l++.

Với cách duy trì bảng tần suất này, mỗi bước mở rộng hay thu hẹp vẫn chỉ tốn O(1) phép gán. Bạn có thể giải ngay bài toán kinh điển "Tìm xâu con dài nhất không chứa ký tự lặp lại" (giữ điều kiện cnt[s[r]] <= 1) hoặc "Tìm đoạn con dài nhất chứa không quá K giá trị khác nhau" (giữ điều kiện distinct <= K) chỉ trong thời gian tuyến tính O(n).

Vì sao có vòng while nằm trong vòng for mà vẫn là O(n)?

Đây là điểm hay nhất của cửa sổ trượt co giãn. Thoạt nhìn, vòng while (cur > S) nằm bên trong vòng for (int r = 0; r < n; ++r) trông giống hệt hai vòng lặp lồng nhau O(n²).

Nhưng hãy nhìn vào biến l:

• Biến l khởi tạo bằng 0 ở ngoài cùng.
• Mỗi lần thân vòng while chạy, l lại tăng lên 1 (l++) và không bao giờ bị đặt lại về 0.
• Do l không thể vượt quá n, nên tính gộp trên toàn bộ cả chương trình, thân vòng while chỉ có thể thực hiện tối đa n lần!

Cộng n bước của vòng for với tối đa n bước của vòng while, tổng số phép tính chỉ là 2n, tức độ phức tạp thời gian là O(n) và bộ nhớ phụ là O(1).

Khi nào dùng được Cửa sổ trượt, khi nào không?

Lỗi hay gặp

Luyện ngay trên Big-O Coding

Thử sức ngay với các bài tập áp dụng trực tiếp kỹ thuật cửa sổ trượt trên hệ thống Big-O Coding:

Câu hỏi thường gặp

Nguồn tham khảo

• USACO Guide: Two Pointers & Sliding Window
• CSES Competitive Programmer's Handbook — Chapter 8: Sliding Window
• Big-O Coding: Lộ trình Zero-100