Kỹ thuật hai con trỏ (Two Pointers): Vũ khí biến thuật toán O(N²) thành O(N) siêu tốc

Trong lập trình thi đấu, có những bài toán khi mới đọc đề bạn sẽ nghĩ ngay đến việc viết 2 vòng for lồng nhau để xét mọi cặp phần tử (i, j). Tuy nhiên, khi kích thước dữ liệu tăng lên N = 10^5, thuật toán O(N^2) đó sẽ ngay lập tức bị loại bỏ bởi giới hạn 1.0 giây của máy chấm.

Kỹ thuật hai con trỏ (Two Pointers) là một trong những phương pháp tối ưu giải thuật thanh lịch và hiệu quả nhất. Bằng cách duy trì 2 biến chỉ số (pointers) di chuyển có định hướng trên mảng, nó giúp bạn giải quyết bài toán chỉ trong một lượt duyệt tuyến tính O(N) duy nhất.

1. Ba mô hình kinh điển của kỹ thuật Two Pointers

Mô hình 1: Hai con trỏ đối đầu (Chạy ngược chiều từ 2 đầu mảng)

Thường áp dụng khi mảng đã được sắp xếp tăng dần. Hai con trỏ xuất phát tại 2 cực: left = 0 và right = N - 1, sau đó di chuyển dần vào giữa.

Bài toán mẫu (2Sum Sorted): Cho mảng đã sắp xếp tăng dần. Tìm xem có tồn tại 2 phần tử a[left] + a[right] = K hay không?

• Nếu a[left] + a[right] == K: Tìm thấy đáp án!
• Nếu a[left] + a[right] < K: Tổng hiện tại nhỏ hơn K → Do mảng tăng dần, muốn tăng tổng thì bắt buộc phải tăng phần tử nhỏ hơn: left++.
• Nếu a[left] + a[right] > K: Tổng hiện tại lớn hơn K → Muốn giảm tổng thì bắt buộc phải giảm phần tử lớn hơn: right--.

#include <bits/stdc++.h>
using namespace std;

bool findPair(const vector<int>& a, int k) {
    int left = 0, right = (int)a.size() - 1;
    while (left < right) {
        int sum = a[left] + a[right];
        if (sum == k) return true;
        else if (sum < k) left++;
        else right--;
    }
    return false;
}

Mô hình 2: Cửa sổ trượt (Sliding Window — Hai con trỏ cùng chiều)

Cả left và right cùng xuất phát từ đầu mảng và di chuyển về phía cuối mảng. Con trỏ right liên tục nạp thêm phần tử mới để mở rộng cửa sổ, và khi điều kiện bị vi phạm, con trỏ left sẽ dịch sang phải để thu hẹp cửa sổ lại.

Bài toán mẫu: Cho mảng N số nguyên dương và số K. Tìm độ dài đoạn con liên tiếp dài nhất có tổng không vượt quá K.

#include <bits/stdc++.h>
using namespace std;

int longestSubarray(const vector<int>& a, long long k) {
    int left = 0, max_len = 0;
    long long current_sum = 0;
    
    for (int right = 0; right < (int)a.size(); right++) {
        current_sum += a[right]; // Mở rộng cửa sổ về bên phải
        
        // Co cửa sổ lại từ bên trái khi tổng vi phạm điều kiện
        while (current_sum > k && left <= right) {
            current_sum -= a[left];
            left++;
        }
        
        max_len = max(max_len, right - left + 1);
    }
    
    return max_len;
}

Mô hình 3: Hai con trỏ trên hai mảng khác nhau (Trộn mảng)

Cho 2 mảng A (kích thước N) và B (kích thước M) đều đã được sắp xếp tăng dần. Hãy trộn chúng thành một mảng C đã sắp xếp kích thước N + M trong thời gian O(N + M) (đây chính là thao tác Merge trong thuật toán MergeSort):

vector<int> mergeSorted(const vector<int>& A, const vector<int>& B) {
    int i = 0, j = 0;
    vector<int> C;
    while (i < (int)A.size() && j < (int)B.size()) {
        if (A[i] <= B[j]) {
            C.push_back(A[i++]);
        } else {
            C.push_back(B[j++]);
        }
    }
    // Nối nốt các phần tử còn lại
    while (i < (int)A.size()) C.push_back(A[i++]);
    while (j < (int)B.size()) C.push_back(B[j++]);
    return C;
}

2. Tại sao vòng while nằm trong vòng for mà vẫn chạy O(N)?

Đây là câu hỏi rất nhiều bạn thắc mắc khi học kỹ thuật Sliding Window: "Em thấy có vòng while nằm lồng trong vòng for, chẳng lẽ nó không phải là O(N^2) sao?"

Câu trả lời là KHÔNG: Hãy quan sát chuyển động của con trỏ left:

• Con trỏ right tăng dần từ 0 đến N - 1 (chạy đúng N bước).
• Con trỏ left chỉ đi tiến sang phải, tuyệt đối không bao giờ quay lùi lại.
• Trong suốt toàn bộ thời gian chạy của chương trình, con trỏ left cũng chỉ tăng tối đa N lần!

Vì vậy, tổng số thao tác tăng con trỏ của cả hai con trỏ tối đa chỉ là N + N = 2N bước. Do đó độ phức tạp đạt chuẩn tuyến tính O(N) tuyệt đối!