Giải Mã Thuật Toán Sliding Window: Tuyệt Chiêu Biến O(n^2) Thành O(n) Trong Một Nốt Nhạc

Trong các buổi phỏng vấn Technical tại NCC hay khi đối mặt với các bài toán xử lý mảng (Array/String) trên LeetCode, chúng ta rất dễ rơi vào cái bẫy mang tên Brute Force (Vét cạn). Cách tiếp cận này thường dùng 2 vòng lặp lồng nhau, khiến độ phức tạp thuật toán nhảy vọt lên $O(n^2)$ và lập tiếp nhận kết quả “Time Limit Exceeded” khi gặp dữ liệu lớn.

Có một kỹ thuật cực kỳ tối ưu, giúp bạn “gộp” 2 vòng lặp đó lại thành 1 vòng lặp duy nhất với độ phức tạp tuyến tính $O(n)$. Đó chính là Sliding Window (Kỹ thuật Cửa sổ trượt).

Hãy cùng giải mã kỹ thuật này để xem nó có gì mà “thần thánh” đến vậy!

1. Bản chất của kỹ thuật Sliding Window là gì?

Hãy tưởng tượng bạn đang nhìn qua một ô cửa sổ có kích thước cố định hoặc linh hoạt. Ô cửa sổ này sẽ “trượt” từ đầu mảng đến cuối mảng dữ liệu. Thay vì tính toán lại toàn bộ các phần tử nằm trong cửa sổ ở mỗi bước dịch chuyển, chúng ta chỉ cần cập nhật sự thay đổi khi cửa sổ đón nhận phần tử mới ở phía trước và bỏ lại phần tử cũ ở phía sau.

Ý tưởng cốt lõi:

Tận dụng kết quả của bước tính toán trước đó để phục vụ cho bước tiếp theo, loại bỏ hoàn toàn việc tính toán trùng lặp.

Bước 1: [1,  3,  -1], -3,  5,  3,  6,  7   -> Tổng = 3
          |       |
Bước 2:  1, [3,  -1,  -3], 5,  3,  6,  7   -> Tổng mới = 3 - 1 + (-3) = -1
              |       |
(Cửa sổ dịch sang phải: Trừ đi phần tử vừa ra khỏi cửa sổ, Cộng thêm phần tử mới vào)

(Hình 1: Mô phỏng cơ chế dịch chuyển của Cửa sổ trượt / Alt: Mô phỏng thuật toán Sliding Window trên mảng số nguyên)

2. Bài toán thực tế: Tìm mảng con có tổng lớn nhất

Để hiểu rõ sức mạnh của Sliding Window, hãy cùng giải quyết một bài toán kinh điển: Cho một mảng số nguyên và một số nguyên $k$. Hãy tìm tổng lớn nhất của $k$ phần tử liên tiếp trong mảng.

Cách 1: Tiếp cận kiểu Brute Force (Dùng 2 vòng lặp)

Ý tưởng là duyệt qua từng phần tử, ứng với mỗi phần tử lại chạy một vòng lặp nữa để tính tổng $k$ phần tử tiếp theo.

JavaScript

function maxSubarraySumBruteForce(arr, k) {
    if (arr.length < k) return 0;
    let maxSum = -Infinity;

    // Vòng lặp 1: Duyệt qua các điểm bắt đầu có thể có
    for (let i = 0; i <= arr.length - k; i++) {
        let currentSum = 0;
        // Vòng lặp 2: Tính tổng k phần tử tiếp theo
        for (let j = 0; j < k; j++) {
            currentSum += arr[i + j];
        }
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
}

• Độ phức tạp thời gian (Time Complexity): $O(n \cdot k)$. Nếu $k$ xấp xỉ bằng $n$, thuật toán sẽ biến thành $O(n^2)$. Hệ thống sẽ bị nghẽn nếu mảng có hàng triệu phần tử.

Cách 2: Áp dụng Sliding Window (1 vòng lặp duy nhất)

Thay vì tính lại từ đầu, khi dịch cửa sổ sang phải 1 bước, ta chỉ cần lấy Tổng cũ + Phần tử mới bên phải – Phần tử cũ vừa ra khỏi bên trái.

JavaScript

function maxSubarraySumSlidingWindow(arr, k) {
    if (arr.length < k) return 0;

    let maxSum = 0;
    let currentSum = 0;

    // 1. Tính tổng của "cửa sổ" đầu tiên có kích thước k
    for (let i = 0; i < k; i++) {
        currentSum += arr[i];
    }
    maxSum = currentSum;

    // 2. Bắt đầu "trượt" cửa sổ từ vị trí k đến hết mảng
    for (let i = k; i < arr.length; i++) {
        // Cộng phần tử mới đi vào (arr[i]), trừ phần tử cũ đi ra (arr[i - k])
        currentSum = currentSum + arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

• Độ phức tạp thời gian (Time Complexity): $O(n)$. Chúng ta chỉ đi qua mảng đúng một lần duy nhất. Tốc độ xử lý tăng lên rõ rệt!

3. Khi nào nên áp dụng Sliding Window?

Không phải bài toán mảng nào cũng dùng được kỹ thuật này. Bạn hãy nghĩ ngay đến Sliding Window nếu bài toán xuất hiện các dấu hiệu “nhận biết” sau:

1. Kiểu dữ liệu: Đề bài yêu cầu xử lý trên một chuỗi (String), mảng (Array) hoặc danh sách liên kết (Linked List).
2. Từ khóa tìm kiếm: Yêu cầu tìm mảng con (subarray), chuỗi con (substring) thỏa mãn một điều kiện nào đó dài nhất, ngắn nhất hoặc có tổng/trung bình lớn nhất.
3. Tính liên tiếp: Các phần tử trong mảng con bắt buộc phải nằm kề nhau (contiguous).

Các biến thể của Sliding Window:

• Cửa sổ có kích thước cố định (Fixed-size Window): Giống như ví dụ tìm tổng của $k$ phần tử ở trên. Kích thước cửa sổ không đổi, chỉ dịch chuyển.
• Cửa sổ có kích thước linh hoạt (Dynamic-size Window): Cửa sổ có thể tự co giãn dựa trên điều kiện của đề bài. Bạn có thể tham khảo thêm cách vận dụng cấu trúc dữ liệu linh hoạt này qua bài viết Tối ưu hóa hiệu năng ứng dụng với Redis Caching trên NCC Ant để thấy rõ tầm quan trọng của việc quản lý bộ nhớ đệm khi xử lý dữ liệu lớn.

4. Bảng tổng hợp so sánh hiệu năng

Dưới đây là sự khác biệt trực quan về mặt hiệu năng giữa hai cách tiếp cận khi kích thước mảng ($n$) tăng lên:

Kết luận & Takeaways

Sliding Window không chỉ là một kỹ thuật giúp bạn “vượt ải” các bài phỏng vấn khắt khe, mà nó còn là tư duy tối ưu hóa mã nguồn trong thực tế. Khi viết code xử lý dữ liệu lớn trên Backend hay Frontend, việc giảm bớt các vòng lặp lồng nhau sẽ giúp ứng dụng tiết kiệm CPU và tăng tốc độ phản hồi cho người dùng.

Takeaways ngắn gọn cần nhớ:

• Cửa sổ trượt giúp biến độ phức tạp từ $O(n^2)$ về $O(n)$ bằng cách tận dụng kết quả tính toán trước đó.
• Chỉ áp dụng khi bài toán yêu cầu xử lý mảng con liên tiếp.
• Công thức dịch chuyển: Tổng mới = Tổng cũ + Phần tử vào - Phần tử ra.

Để luyện tập thêm về kỹ thuật này, bạn có thể thử sức ngay với các bài toán kinh điển trên các nền tảng lập trình thi đấu như: LeetCode 209 – Minimum Size Subarray Sum hoặc LeetCode 438 – Find All Anagrams in a String.

Bạn đã từng tối ưu thành công đoạn code nào trong dự án thực tế bằng giải pháp tương tự chưa? Hay có bài toán nào đang làm khó bạn mà nghi vấn là dùng Sliding Window không? Hãy để lại bình luận phía dưới để các anh em Tech-er tại NCC cùng thảo luận và hiến kế nhé!