Kỹ thuật hai con trỏ (Two Pointers): giải thích từng bước, code C++ và Python

Kỹ thuật hai con trỏ là gì?

Khi cần tìm hai phần tử trong mảng thỏa mãn một điều kiện nào đó (ví dụ: tìm hai số có tổng bằng X), cách nghĩ tự nhiên nhất là dùng hai vòng lặp lồng nhau: vòng ngoài cố định phần tử thứ nhất a[i], vòng trong thử mọi phần tử thứ hai a[j] đứng sau nó. Cách vét cạn này xét toàn bộ n(n - 1) / 2 cặp, tức có độ phức tạp là O(n²).

Tuy nhiên, nếu mảng đã được sắp xếp tăng dần, mỗi lần so sánh tổng a[l] + a[r] với X cho phép ta loại bỏ ngay cả một hàng dài các cặp không cần thử:

• Đặt chỉ số l = 0 ở đầu mảng (phần tử nhỏ nhất) và r = n - 1 ở cuối mảng (phần tử lớn nhất).
• Nếu a[l] + a[r] > X: vì a[l] đã là số nhỏ nhất đang còn lại mà cộng với a[r] vẫn lớn hơn X, nên a[r] cộng với bất kỳ số nào khác trong đoạn cũng đều lớn hơn X. Ta loại ngay a[r] bằng cách giảm r đi 1 (r--).
• Nếu a[l] + a[r] < X: vì a[r] đã là số lớn nhất đang còn lại mà cộng với a[l] vẫn chưa đủ X, nên a[l] không thể ghép với số nào để đạt X. Ta loại ngay a[l] bằng cách tăng l lên 1 (l++).
• Nếu a[l] + a[r] == X: ta đã tìm thấy cặp cần tìm!

Cách điều khiển hai chỉ số l và r phối hợp nhịp nhàng như vậy được gọi là kỹ thuật hai con trỏ (two pointers).

Ví dụ từng bước: Tìm cặp phần tử có tổng bằng 14

Cho mảng tăng dần 7 phần tử a = [1, 2, 4, 6, 8, 10, 15] và cần tìm hai vị trí có tổng bằng X = 14. Hãy theo dõi 4 bước dịch chuyển của L và R:

Code tìm cặp có tổng bằng X bằng C++ và Python

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

// Tìm hai vị trí (l, r) với l < r trong mảng tăng dần a sao cho a[l] + a[r] == x
pair<int, int> timCapTongX(const vector<int>& a, int x) {
    int l = 0, r = (int)a.size() - 1;
    while (l < r) {
        long long tong = (long long)a[l] + a[r];
        if (tong == x) return {l, r};
        if (tong < x) l++;   // cần tổng lớn hơn -> dịch con trỏ trái sang phải
        else r--;            // cần tổng nhỏ hơn -> dịch con trỏ phải sang trái
    }
    return {-1, -1};
}

int main() {
    vector<int> a = {1, 2, 4, 6, 8, 10, 15};
    auto [l1, r1] = timCapTongX(a, 14);
    auto [l2, r2] = timCapTongX(a, 20);
    cout << l1 << " " << r1 << "\n";  // 2 5
    cout << l2 << " " << r2 << "\n";  // -1 -1
    return 0;
}

def tim_cap_tong_x(a, x):
    """Tìm hai vị trí (l, r) trong danh sách tăng dần a sao cho a[l] + a[r] == x."""
    l, r = 0, len(a) - 1
    while l < r:
        tong = a[l] + a[r]
        if tong == x:
            return l, r
        if tong < x:
            l += 1  # cần tổng lớn hơn -> tăng l
        else:
            r -= 1  # cần tổng nhỏ hơn -> giảm r
    return -1, -1


a = [1, 2, 4, 6, 8, 10, 15]
print(*tim_cap_tong_x(a, 14))  # 2 5
print(*tim_cap_tong_x(a, 20))  # -1 -1

Nếu mảng đầu vào đề bài cho chưa được sắp xếp, bạn có thể sắp xếp mảng trước trong O(n log n) rồi chạy hai con trỏ trong O(n). Tổng độ phức tạp là O(n log n) — vẫn nhanh hơn rất nhiều so với O(n²) khi n = 100.000. (Nếu đề yêu cầu trả về chỉ số trên mảng gốc chưa sắp xếp, chỉ cần lưu từng phần tử kèm chỉ số ban đầu dưới dạng cặp (giá_trị, vị_trí_cũ) trước khi sắp xếp).

Vì sao hai con trỏ chỉ tốn O(n) bước?

Khi nhìn vào vòng lặp hoặc đặc biệt là các biến thể có vòng while lồng bên trong vòng for, người mới rất dễ tưởng nhầm độ phức tạp là O(n²). Để tính đúng, ta dùng phương pháp đếm tổng số bước dịch chuyển (amortized analysis):

• Ban đầu khoảng cách giữa hai con trỏ là r - l = n - 1.
• Ở mỗi vòng lặp, hoặc l tăng thêm 1, hoặc r giảm đi 1. Không có lệnh nào làm l lùi lại hay làm r tăng lên.
• Do đó, khoảng cách r - l giảm đi đúng 1 sau mỗi bước, nên vòng lặp chạy tối đa n - 1 lần rồi dừng.

Vậy:

• Thời gian: O(n) trên mảng đã sắp xếp.
• Bộ nhớ phụ: O(1) (chỉ dùng hai biến nguyên l và r).

Ba mẫu hai con trỏ phổ biến nhất bạn cần nhớ

Kỹ thuật hai con trỏ không chỉ có kiểu đi từ hai đầu vào giữa. Trong thực tế làm bài, bạn sẽ gặp 3 mẫu chính:

Mẫu 1: Hai con trỏ đi ngược chiều từ hai đầu mảng (l = 0, r = n - 1)

• Khi nào dùng: Tìm cặp có tổng bằng X, tìm cặp có tổng gần X nhất, đếm số cặp có tổng ≤ X, kiểm tra xâu đối xứng (palindrome), đảo ngược mảng tại chỗ, hoặc bài toán chứa nhiều nước nhất (Container With Most Water).
• Quy tắc: Một con trỏ ở đầu trái (l = 0), một con trỏ ở đầu phải (r = n - 1), tiến lại gần nhau cho tới khi l >= r.
• Mẹo đếm số cặp có tổng ≤ X trên mảng tăng dần: Nếu tại bước đang xét mà a[l] + a[r] <= X, thì vì mảng tăng dần nên a[l] ghép với bất kỳ phần tử nào từ vị trí l + 1 đến r cũng đều có tổng ≤ X. Có đúng r - l phần tử như vậy! Ta cộng ngay ans += (r - l) rồi tăng l++ mà không cần duyệt từng phần tử ở giữa. Ngược lại nếu a[l] + a[r] > X, ta chỉ cần giảm r--.

Mẫu 2: Hai con trỏ trên hai mảng khác nhau (i = 0 trên mảng A, j = 0 trên mảng B)

• Khi nào dùng: Gộp hai mảng đã sắp xếp thành một mảng tăng dần (bước Merge cốt lõi của thuật toán Merge Sort), tìm giao của hai mảng tăng dần, tìm cặp một phần tử thuộc A và một phần tử thuộc B có chênh lệch |a[i] - b[j]| nhỏ nhất, hoặc kiểm tra xâu con không liên tiếp (subsequence).
• Quy tắc: So sánh a[i] và b[j], bên nào nhỏ hơn thì đưa vào kết quả (hoặc dịch chuyển để thu hẹp khoảng cách) và nhích con trỏ của mảng đó lên 1.

Hãy xem bảng chạy từng bước khi gộp mảng A = [1, 3, 5, 8] và B = [2, 3, 6, 7]:

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

// Gộp hai mảng tăng dần a và b thành một mảng tăng dần trong O(n + m)
vector<int> gopHaiMang(const vector<int>& a, const vector<int>& b) {
    int i = 0, j = 0;
    vector<int> c;
    c.reserve(a.size() + b.size());
    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++]);
    }
    while (i < (int)a.size()) c.push_back(a[i++]);
    while (j < (int)b.size()) c.push_back(b[j++]);
    return c;
}

int main() {
    vector<int> a = {1, 4, 7, 9};
    vector<int> b = {2, 3, 7, 12};
    vector<int> c = gopHaiMang(a, b);
    for (int k = 0; k < (int)c.size(); ++k) {
        cout << c[k] << (k + 1 == (int)c.size() ? "\n" : " ");  // 1 2 3 4 7 7 9 12
    }
    return 0;
}

def gop_hai_mang(a, b):
    """Gộp hai danh sách tăng dần a và b thành danh sách tăng dần trong O(n + m)."""
    i, j = 0, 0
    c = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
    c.extend(a[i:])
    c.extend(b[j:])
    return c


a = [1, 4, 7, 9]
b = [2, 3, 7, 12]
print(*gop_hai_mang(a, b))  # 1 2 3 4 7 7 9 12

Mẫu 3: Hai con trỏ đi cùng chiều trên một mảng (write và read, hoặc left và right cùng xuất phát từ đầu mảng)

• Khi nào dùng: Xóa phần tử trùng nhau trên mảng đã sắp xếp, dồn tất cả các số 0 về cuối mảng mà vẫn giữ nguyên thứ tự các số khác 0, nén mảng tại chỗ (in-place) với bộ nhớ O(1), hoặc duy trì một đoạn con [left..right] thỏa mãn điều kiện.
• Cơ chế con trỏ đọc – ghi (read / write): Con trỏ read đi lướt qua từng phần tử từ 0 đến n - 1 để kiểm tra. Mỗi khi gặp phần tử hợp lệ (ví dụ phần tử khác với phần tử vừa ghi trước đó a[read] != a[write]), ta tăng write++ và chép a[write] = a[read]. Kết thúc vòng lặp, đoạn 0 .. write chứa toàn bộ các phần tử phân biệt mà không tốn thêm bất kỳ mảng phụ nào.
• Khi đoạn [left..right] được dùng như một khung trượt dọc theo mảng để tính tổng hoặc đếm tần suất, mẫu này chính là Kỹ thuật cửa sổ trượt (Sliding Window).

So sánh Hai con trỏ với Vét cạn, Tìm kiếm nhị phân và Bảng băm

Cùng một bài toán tìm cặp phần tử có tổng bằng X, bạn có tới 4 cách tiếp cận. Bảng dưới đây giúp bạn chọn đúng công cụ theo ràng buộc của đề bài:

Lỗi hay gặp

Luyện ngay trên Big-O Coding

Áp dụng ngay kỹ thuật hai con trỏ vào các bài tập dưới đây 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
• CSES Competitive Programmer's Handbook — Chapter 8: Amortized Analysis
• cppreference: std::merge