Giải thuật Two Pointer (hoặc còn gọi là "hai con trỏ") là một kỹ thuật giải quyết các bài toán có liên quan đến chuỗi, mảng hoặc dãy số bằng cách sử dụng hai con trỏ di chuyển qua dữ liệu mục tiêu. Giải thuật này thường được sử dụng để tối ưu hóa thời gian thực hiện bằng cách giảm số lần duyệt qua dữ liệu.

Có hai biến thể chính của giải thuật Two Pointer:

Two Pointers Song Song (Parallel Pointers): Trong trường hợp này, hai con trỏ hoặc chỉ mục di chuyển cùng một hướng trên dãy dữ liệu. Thường được sử dụng để tìm kiếm hoặc kiểm tra sự tồn tại của một phần tử trong dãy, hoặc để tính toán khoảng cách giữa hai phần tử trong dãy.

Two Pointers Ngược Chiều (Opposite Pointers): Trong trường hợp này, hai con trỏ hoặc chỉ mục di chuyển theo hai hướng khác nhau trên dãy dữ liệu. Thường được sử dụng để giải quyết các bài toán liên quan đến tìm kiếm, sắp xếp hoặc xử lý dãy số, ví dụ như tìm kiếm cặp phần tử có tổng bằng một giá trị cụ thể.

Giải thuật Two Pointer thường là một phương pháp hiệu quả để giải quyết các bài toán có thời gian thực hiện O(n) hoặc O(nlogn) trong khi sử dụng không gian bổ sung O(1), nghĩa là không cần dùng thêm bộ nhớ đáng kể. Nó được sử dụng rộng rãi trong lập trình cạnh sắc và giải quyết nhiều bài toán thú vị như tìm kiếm dãy con có tổng bằng một giá trị, xác định dãy con liên tiếp dài nhất có tổng bằng một giá trị, và nhiều bài toán liên quan khác Ví dụ: Cho dãy số nguyên ~A~ có ~N~ phần tử (N ≤ 10 ⁵; ~A~ _i ≤ 10₉) và một số nguyên dương ~M~ hãy đếm xem có bao nhiêu cặp giá trị có tổng giá trị bằng ~M~

• Nếu sử dụng cày trâu để duyệt qua dãy số 2 lần ta có độ phức tạp là o(~N~²) chỉ giải quyết được với dãy có số lượng phần tử ≤ 10⁴ do đó không giải quyết hết bài toán.
• Nếu ta sắp xếp dãy đã cho theo thứ tự không giảm sau đó sử dụng 2 con trỏ ngược chiều để kiểm tra tổng giá trị của 2 con trỏ. Nếu tổng bé hơn ~M~ thì dịch chuyển con trỏ bên trái sang phải 1 vị trí, nếu tổng lớn hơn ~M~ thì dịch chuyển con trỏ bên phải sang trái 1 vị trí, nếu tổng bằng ~M~ thì tăng giá trị biến đếm và dịch chuyển con trỏ bên trái hoặc bên phải phải tùy trường hợp
• Điều kiện dừng của 2 con trỏ tùy thuộc vào đề bài cụ thể
• Nếu là dãy sắp xếp thì có thể giải quyết được bài toán có số phần tử lên đến 10₈
• Ví dụ 1: Cho hai dãy số nguyên ~A~ và ~B~ mỗi dãy có ~N~ phần tử (N ≤ 10⁵) hãy tìm hai chỉ số ~i~, ~j~ của 2 dãy sao cho A_i + B_j là bé nhất
• Ví dụ 2: Cho hai dãy số nguyên đã sắp xếp ~A~ và ~B~ mỗi dãy lần lượt có ~N~ và ~M~ phần tử (0 < ~M~, ~N~ ≤ 10⁷) hãy tạo ra dãy C bằng cách ghép 2 dãy trên lại với nhau và tạo thành dãy được sắp xếp
• Ví dụ 3: Cho mảng số nguyên A có N phần tử. Hãy cho biết có bao nhiêu dãy con tổng các phần tử bằng 0
• Ví dụ 4: Cho mảng số nguyên A có N phần tử. Hãy tìm dãy con dài nhất có tổng các phần tử chia hết cho 1 số nguyên K cho trước
• Ps: Hai con trỏ là kỹ thuật được sử dụng rất nhiều trong lập trình thi đấu và trong những cuộc thi như THT, HSG đây là câu hỏi để phân loại giải.