Kỹ Thuật Hai Con Trỏ

1. Khái niệm & nguyên lý hoạt động

Kỹ thuật Hai con trỏ (Two Pointers Technique) là phương pháp sử dụng hai biến chỉ số (thường ký hiệu là $L$ và $R$) duyệt trên cấu trúc dữ liệu tuyến tính (mảng hoặc chuỗi) nhằm thu hẹp không gian tìm kiếm từ $\mathcal{O}(N^2)$ xuống $\mathcal{O}(N)$.

Trong mô hình Hai con trỏ đối đầu (Opposite-direction Two Pointers):

• Con trỏ trái $L$ khởi tạo tại đầu mảng ($L = 0$).
• Con trỏ phải $R$ khởi tạo tại cuối mảng ($R = N - 1$).
• Dãy số bắt buộc phải có tính đơn điệu (thường là mảng đã sắp xếp tăng dần $A_0 \le A_1 \le \dots \le A_{N-1}$).

Tại mỗi bước, thuật toán tính toán một hàm mục tiêu trên cặp phần tử $(A_L, A_R)$ (ví dụ: $\text{Sum} = A_L + A_R$) và so sánh với giá trị đích $S$:

• Nếu $\text{Sum} == S$: Tìm thấy nghiệm hợp lệ.
• Nếu $\text{Sum} < S$: Tổng hiện tại nhỏ hơn mục tiêu $\implies$ Tăng con trỏ trái (++L) để tìm kiếm tổng lớn hơn.
• Nếu $\text{Sum} > S$: Tổng hiện tại lớn hơn mục tiêu $\implies$ Giảm con trỏ phải (--R) để tìm kiếm tổng nhỏ hơn.

2. Chứng minh bất biến lặp (loop invariant) & tính đúng đắn

2.1. Phát biểu bất biến lặp

Bất biến lặp: Tại bất kỳ thời điểm nào trong quá trình thực thi, nếu tồn tại một cặp nghiệm $(i, j)$ thỏa mãn $A_i + A_j = S$ ($i < j$), thì cặp nghiệm đó chắc chắn nằm trọn vẹn trong đoạn chỉ số đang xét: $L \le i < j \le R$.

2.2. Chứng minh quy nạp toán học

1. Khởi tạo: Ban đầu $L = 0, R = N - 1$, đoạn $[L, R]$ bao phủ toàn bộ mảng, bất biến lặp hiển nhiên đúng.
2. Duy trì: Giả sử bất biến lặp đúng tại bước hiện tại $[L, R]$. * Trường hợp 1: $A_L + A_R > S$ (Thao tác --R):

Vì mảng tăng dần, với mọi chỉ số $k \in [L, R-1]$, ta luôn có $A_k \ge A_L \implies A_k + A_R \ge A_L + A_R > S$.

Do đó, phần tử $A_R$ không thể tạo thành tổng $S$ với bất kỳ phần tử nào trong đoạn $[L, R-1]$. Việc loại bỏ $R$ bằng cách giảm $R \to R - 1$ không làm mất bất kỳ nghiệm hợp lệ nào.

• Trường hợp 2: $A_L + A_R < S$ (Thao tác ++L): Vì mảng tăng dần, với mọi chỉ số $k \in [L+1, R]$, ta luôn có $A_k \le A_R \implies A_L + A_k \le A_L + A_R < S$. Do đó, phần tử $A_L$ không thể tạo thành tổng $S$ với bất kỳ phần tử nào trong đoạn $[L+1, R]$. Việc loại bỏ $L$ bằng cách tăng $L \to L + 1$ là an toàn $100\%$.

1. Kết thúc: Vòng lặp dừng khi $L \ge R$. Nếu không tìm thấy nghiệm, chứng tỏ không tồn tại cặp $(i, j)$ nào thỏa mãn $A_i + A_j = S$.

3. Các mô hình bài toán đặc trưng

3.1. Mô hình 1: Tìm cặp số có tổng đúng bằng $S$ (two sum)

• Mục tiêu: Tìm $i < j$ sao cho $A_i + A_j = S$.
• Quy tắc di chuyển:
• Nếu $A_L + A_R < S \implies L \leftarrow L + 1$ (Tổng nhỏ hơn mục tiêu, tăng cận dưới).

• Nếu $A_L + A_R > S \implies R \leftarrow R - 1$ (Tổng lớn hơn mục tiêu, giảm cận trên).

• Nếu $A_L + A_R = S \implies$ Ghi nhận nghiệm và dừng thuật toán.

Ví dụ minh họa 1: Tìm cặp số có tổng $S = 14$

Cho mảng $N = 6$ phần tử đã sắp xếp: $A = [2, 3, 5, 8, 11, 15]$ (0-based indexing).

Bảng mô phỏng từng bước lặp Hai con trỏ:

3.2. Mô hình 2: Đếm số cặp có tổng thỏa mãn bất đẳng thức $A_i + A_j \le S$

• Mục tiêu: Đếm số lượng cặp $(i, j)$ với $i < j$ thỏa mãn $A_i + A_j \le S$.

• Khai thác tổ hợp: Nếu tại bước $(L, R)$ ta có $A_L + A_R \le S$, thì do mảng tăng dần, mọi phần tử $A_k$ với $L < k \le R$ khi ghép với $A_L$ đều thỏa mãn: $$A_L + A_k \le A_L + A_R \le S$$ Do đó, có đúng $R - L$ cặp hợp lệ xuất phát từ $L$: $(L, L+1), (L, L+2), \dots, (L, R)$.

• Thao tác: Cộng $(R - L)$ vào kết quả đếm, sau đó tăng $L \leftarrow L + 1$. Ngược lại, nếu $A_L + A_R > S$, giảm $R \leftarrow R - 1$.

Ví dụ minh họa 2: Đếm số cặp có tổng $\le 10$ trên mảng $A = [1, 2, 4, 7, 9]$

3.3. Mô hình 3: Ghép cặp cực trị tham lam (bài toán thuyền cứu hộ / xe chở hàng)

• Bài toán: Mỗi xe chở tối đa 2 kiện hàng có tổng trọng lượng $\le C$. Tìm số xe ít nhất để chở hết $N$ kiện hàng.
• Chiến lược: Sắp xếp mảng trọng lượng tăng dần. Đặt $L = 0, R = N - 1$.
• Thử ghép kiện nặng nhất $A_R$ với kiện nhẹ nhất $A_L$.
• Nếu $A_L + A_R \le C$: Cả hai kiện đi chung xe $\implies L \leftarrow L + 1, R \leftarrow R - 1$.

• Nếu $A_L + A_R > C$: Kiện $A_R$ buộc phải đi xe riêng $\implies R \leftarrow R - 1$.

• Mỗi lần lặp tốn 1 xe (++ans).

3.4. Mô hình 4: Khử chiều đa biến (bài toán 3-sum và 4-sum)

• Bài toán 3-Sum: Tìm bộ ba $(i, j, k)$ có tổng $A_i + A_j + A_k = S$.
• Chiến lược: Sắp xếp mảng. Cố định phần tử thứ nhất $i$ từ $0$ đến $N - 3$, chuyển bài toán về tìm 2 số trong đoạn $[i+1 \dots N-1]$ có tổng bằng $S - A_i$ bằng Two Pointers.
• Độ phức tạp: Giảm từ $\mathcal{O}(N^3)$ xuống $\mathcal{O}(N^2)$.

4. Phân tích độ phức tạp thời gian & không gian

• Thời gian (Time Complexity):
• Bước sắp xếp: $\mathcal{O}(N \log N)$.
• Bước duyệt Hai con trỏ: $\mathcal{O}(N)$ (do tại mỗi phép so sánh, ít nhất một trong hai con trỏ di chuyển 1 bước, tổng số bước di chuyển tối đa là $N$).
• Tổng thời gian: $\mathcal{O}(N \log N + N) = \mathcal{O}(N \log N)$.
• Không gian bộ nhớ (Space Complexity):
• $\mathcal{O}(1)$ bộ nhớ phụ trợ khi xử lý trực tiếp trên mảng (in-place).

5. Mẫu cài đặt chuẩn thi đấu (competitive template)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long s;
    if (!(cin >> n >> s)) return 0;

    vector<long long> a(n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];

    }

    // Bước 1: Sắp xếp mảng tạo tính đơn điệu O(N log N)
    sort(a.begin(), a.end());

    // Bước 2: Khởi tạo Hai con trỏ đối đầu O(N)
    int l = 0, r = n - 1;
    bool found = false;

    while (l < r) {
        long long current_sum = a[l] + a[r];
        if (current_sum == s) {
            cout << a[l] << " " << a[r] << "\n";
            found = true;
            break;
        } else if (current_sum < s) {
            ++l; // Tổng nhỏ hơn mục tiêu -> tăng giá trị cận dưới

        } else {
            --r; // Tổng lớn hơn mục tiêu -> giảm giá trị cận trên

        }
    }

    if (!found) {
        cout << -1 << "\n";
    }

    return 0;
}

6. Các bẫy lỗi kỹ thuật thường gặp (bug traps)

1. Bẫy điều kiện dừng l <= r thay vì l < r: Khi $L = R$, phần tử $A_L$ tự cộng với chính nó ($2 \cdot A_L$), vi phạm yêu cầu chọn hai vị trí phân biệt ($i < j$).
2. Bẫy tràn số nguyên 32-bit: Khi các phần tử $A_i \approx 10^9$, tổng $A_L + A_R$ có thể đạt $2 \cdot 10^9$, suýt soát giới hạn kiểu int ($2^{31}-1$). Bắt buộc sử dụng long long cho biến tính tổng.
3. Bẫy mảng chưa sắp xếp: Áp dụng Hai con trỏ trên mảng chưa có trật tự đơn điệu sẽ dẫn đến sai lệch logic hoàn toàn.