Tổng quan
Kỹ thuật Hai Con Trỏ (Two Pointers) là một mẫu xử lý mảng cốt lõi cho các bài toán trên mảng đã sắp xếp. Thay vì kiểm tra mọi cặp bằng vòng lặp lồng nhau, nó đặt một con trỏ ở đầu và một con trỏ ở cuối, rồi di chuyển chúng lại gần nhau dựa trên việc tổng của chúng so với giá trị mục tiêu như thế nào.
Với bài toán tổng-cặp kinh điển — tìm hai số cộng lại bằng một mục tiêu — kỹ thuật này biến phép quét vét cạn O(n²) thành một lượt duy nhất O(n) với O(1) bộ nhớ phụ. Chính thứ tự đã sắp xếp khiến việc quyết định dịch con trỏ nào trở nên an toàn và rõ ràng.
Hai con trỏ hoạt động thế nào?
- Bắt đầu với mảng đã được sắp xếp tăng dần — đây là điều kiện tiên quyết mà kỹ thuật này dựa vào.
- Đặt con trỏ trái ở phần tử đầu tiên và con trỏ phải ở phần tử cuối cùng.
- Tính tổng hai giá trị được trỏ tới và so sánh với giá trị mục tiêu.
- Nếu tổng quá nhỏ, dịch con trỏ trái sang phải để tăng tổng; nếu tổng quá lớn, dịch con trỏ phải sang trái để giảm tổng.
- Dừng lại khi tổng bằng mục tiêu (đã tìm được cặp) hoặc khi hai con trỏ vượt qua nhau (không tồn tại cặp như vậy).
Khi nào nên dùng?
- Bài toán Two Sum trên mảng đã sắp xếp và 3Sum — những câu hỏi phỏng vấn lập trình nền tảng.
- Kiểm tra chuỗi đối xứng (palindrome) hoặc đảo mảng tại chỗ bằng cách cho hai con trỏ đi vào từ hai đầu.
- Trộn hai mảng đã sắp và bài toán 'container with most water', khi mỗi bước dịch con trỏ ràng buộc hơn.
- Bất kỳ bài toán nào mà một mảng đã sắp cho phép loại bỏ một nửa không gian tìm kiếm chỉ bằng một phép so sánh.
Phân tích độ phức tạp
Mỗi con trỏ chỉ luôn di chuyển vào trong, nên tổng cộng chúng duyệt mảng nhiều nhất một lần, cho thời gian O(n). Chỉ hai chỉ số được lưu, nên bộ nhớ phụ là O(1). Lưu ý con số O(n) giả định mảng đã được sắp xếp; nếu phải sắp xếp trước, bước đó chiếm ưu thế với O(n log n).
Câu hỏi thường gặp
Vì sao mảng phải được sắp xếp?
Việc sắp xếp khiến mỗi bước dịch trở nên rõ ràng: khi tổng quá nhỏ đáp án chỉ có thể nằm bên phải, còn khi quá lớn thì chỉ nằm bên trái. Trên mảng chưa sắp, đảm bảo đó biến mất, nên bạn sẽ cần dùng một tập băm (hash set) thay thế.
Hai con trỏ tốt hơn vòng lặp lồng nhau vét cạn ở điểm nào?
Tìm cặp vét cạn kiểm tra mọi tổ hợp trong O(n²). Hai con trỏ xét mỗi phần tử nhiều nhất một lần, giảm bài toán tìm tổng-cặp xuống O(n) thời gian và O(1) bộ nhớ trên mảng đã sắp.
Hai con trỏ có tìm được tất cả các cặp, không chỉ một cặp, không?
Có. Sau khi tìm được một cặp hợp lệ, dịch cả hai con trỏ vào trong (bỏ qua phần tử trùng lặp) và tiếp tục quét đến khi chúng vượt nhau. Đây chính là cách 3Sum dùng một lượt hai con trỏ bên trong để thu thập mọi bộ ba duy nhất.