Kỹ thuật Sliding Window: Tuyệt chiêu xử lý Mảng con và Chuỗi con trong O(n)

Nếu kỹ thuật Two Pointers (Hai con trỏ) thường dùng để tìm một cặp phần tử (pair), thì Sliding Window (Cửa sổ trượt) là phiên bản nâng cấp chuyên trị các bài toán về một dãy các phần tử liên tiếp (Mảng con - Subarray hoặc Chuỗi con - Substring).

Ý tưởng cốt lõi vô cùng thanh lịch: Thay vì tính toán lại từ đầu cho mỗi mảng con, ta duy trì một "cửa sổ". Khi cửa sổ trượt lên 1 bước, ta chỉ việc cộng phần tử mới đi vào và trừ phần tử cũ rớt lại phía sau.

Nhờ vậy, những bài toán ngốn O(n^2) sẽ được ép xuống chỉ còn O(n).

1. Sliding Window Cố Định (Fixed-size Window)

Đây là dạng cơ bản nhất, kích thước của "cửa sổ" luôn được giữ nguyên là K trong suốt quá trình trượt.

Bài toán: Tìm tổng lớn nhất của mảng con có độ dài đúng bằng K.

(Ví dụ: arr = [2, 1, 5, 1, 3, 2], K = 3)

function maxSum(arr, k) {
  let currentSum = 0;
  
  // 1. Tính tổng của cửa sổ đầu tiên
  for (let i = 0; i < k; i++) currentSum += arr[i];
  
  let max = currentSum;

  // 2. Trượt cửa sổ dần sang phải
  for (let i = k; i < arr.length; i++) {
    // Chỉ cần: Cộng đầu mới vào, Trừ đuôi cũ ra
    currentSum += arr[i] - arr[i - k]; 
    max = Math.max(max, currentSum); // Lưu kỷ lục
  }

  return max;
}

Tại sao nó ảo diệu? Thay vì vòng lặp lồng nhau lặp lại việc cộng các số ở giữa, ta tái sử dụng luôn kết quả cũ. Độ phức tạp giảm từ O(n*k) xuống exacly O(n).

2. Sliding Window Co Giãn (Variable-size Window)

Khác với loại cố định, cửa sổ ở dạng này có thể phình to hoặc thu nhỏ tùy thuộc vào điều kiện đề bài.

• Con trỏ right luôn chạy lên phía trước để mở rộng cửa sổ (nạp thêm data).

• Nếu dữ liệu vi phạm điều kiện, con trỏ left sẽ nhích dần lên để thu hẹp cửa sổ (xả bớt data) cho đến khi hợp lệ trở lại.

Bài toán: Tìm mảng con ngắn nhất có tổng $\ge$ target.

(Ví dụ: arr = [2, 1, 5, 2, 3, 2], target = 7)

function minSubArrayLen(target, arr) {
  let minLen = Infinity;
  let sum = 0, left = 0;

  for (let right = 0; right < arr.length; right++) {
    sum += arr[right]; // Mở rộng cửa sổ sang phải

    // Khi cửa sổ đã đủ lớn (Tổng >= target)
    while (sum >= target) { 
      minLen = Math.min(minLen, right - left + 1); // Cập nhật kỷ lục độ dài
      
      sum -= arr[left]; // Thu hẹp cửa sổ từ bên trái
      left++; 
    }
  }

  return minLen === Infinity ? 0 : minLen;
}

Hỏi xoáy đáp xoay: "Khoan đã! Code có vòng while lồng bên trong vòng for, vậy tại sao thời gian chạy lại là O(n) mà không phải O(n^2)?"

Giải đáp: Hãy nhìn vào vòng đời của một phần tử. Mỗi con số trong mảng chỉ lọt vào cửa sổ (qua right) đúng 1 lần, và bị văng ra (qua left) tối đa 1 lần. Số thao tác tối đa là 2 * n (hằng số bỏ đi). Nên tốc độ thực tế vẫn là O(n) chuẩn mực!

3. Dấu hiệu "bắt mạch" bài toán Sliding Window

Làm sao để biết khi nào nên dùng kỹ thuật này lúc thi đấu hoặc phỏng vấn? Hãy tìm sự kết hợp của 3 từ khóa (Keywords) sau trong đề bài:

1. Dữ liệu đầu vào: Thường là Mảng (Array) hoặc Chuỗi (String).

2. Tính liên tục: Tìm Mảng con liên tiếp (Subarray) hoặc Chuỗi con (Substring). (Lưu ý: Nếu đề bảo tìm Dãy con không liên tiếp - Subsequence thì không dùng được).

3. Yêu cầu tối trị: Tìm Max, Min, Dài nhất, Ngắn nhất, hoặc tổng bằng một số K cụ thể.

4. Lời kết

Sliding Window là một Pattern thanh lịch và mang tính ứng dụng rất cao. Không chỉ dùng để giải bài tập, tư duy "duy trì trạng thái thay vì tính lại từ đầu" còn được áp dụng để xử lý stream dữ liệu mạng TCP/IP, hay phân tích biểu đồ chứng khoán theo thời gian thực (đường trung bình động MA).