👉👈 Two Pointers – Kỹ thuật hai con trỏ

🎯 Mục tiêu bài học

1. Đặt vấn đề

1.1. Cách trực tiếp

Duyệt mọi cặp (i,j), mất O(n²).

1.2. Quan sát

• Nếu a[L]+a[R]<X, phải tăng L.
• Nếu a[L]+a[R]>X, phải giảm R.
• Nếu bằng X, đã tìm thấy đáp án.

2. Ba dạng Two Pointers

3. Mô phỏng hai con trỏ đối đầu

4. Hai con trỏ cùng chiều – đoạn dài nhất có tổng ≤ K

5. Hai con trỏ đọc–ghi – loại phần tử trùng

Với mảng đã sắp xếp, read đọc từng phần tử, write chỉ tăng khi gặp giá trị mới.

6. Phân tích thuật toán

7. Code mẫu

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

int main() {
    int n;
    long long target;
    cin >> n >> target;

    vector<long long> a(n);
    for (long long &x : a) cin >> x;

    sort(a.begin(), a.end());

    int left = 0;
    int right = n - 1;

    while (left < right) {
        long long sum = a[left] + a[right];

        if (sum == target) {
            cout << a[left] << ' ' << a[right];
            return 0;
        }

        if (sum < target) left++;
        else right--;
    }

    cout << "NO";
}

int left = 0;
int best = 0;
long long sum = 0;

for (int right = 0; right < n; right++) {
    sum += a[right];

    while (left <= right && sum > k) {
        sum -= a[left];
        left++;
    }

    best = max(best, right - left + 1);
}

int removeDuplicates(vector<int>& a) {
    if (a.empty()) return 0;

    int write = 1;

    for (int read = 1; read < (int)a.size(); read++) {
        if (a[read] != a[write - 1]) {
            a[write] = a[read];
            write++;
        }
    }

    return write;
}

sort(a.begin(), a.end());

for (int i = 0; i < n; i++) {
    if (i > 0 && a[i] == a[i - 1]) continue;

    int left = i + 1;
    int right = n - 1;

    while (left < right) {
        long long sum = 1LL * a[i] + a[left] + a[right];

        if (sum == target) {
            // xử lý bộ ba
            left++;
            right--;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
}

8. Giải thích code

8.1. Vì sao Pair Sum cần mảng đã sắp xếp?

Nhờ thứ tự tăng, tăng L chắc chắn không làm giá trị bên trái giảm; giảm R chắc chắn không làm giá trị bên phải tăng.

8.2. Vì sao điều kiện là left < right?

Hai vị trí phải khác nhau. Nếu bằng nhau, ta đang dùng cùng một phần tử hai lần.

8.3. Vì sao vòng while trong for vẫn O(n)?

8.4. Vì sao Sliding Window cần số không âm?

Nếu có số âm, khi mở rộng R tổng có thể giảm, nên không thể quyết định co L chỉ dựa trên sum > K.

8.5. Vì sao remove duplicates ghi vào a[write]?

Đoạn a[0..write-1] luôn chứa các giá trị duy nhất đã tìm thấy.

9. Lỗi thường gặp

• Dùng Pair Sum Two Pointers trên mảng chưa sắp xếp.
• Quên long long cho tổng.
• Dùng left <= right và dùng một phần tử hai lần.
• Di chuyển sai con trỏ khi tổng nhỏ/lớn hơn target.
• Dùng Sliding Window sum ≤ K với số âm.
• Không bỏ qua phần tử trùng trong 3Sum.
• Không chứng minh tính đơn điệu.

10. Quiz và bài tập