“Các kỹ thuật hiệu quả nhất là những kỹ thuật đơn giản và được thực hiện tốt,” trong Cấu trúc dữ liệu và thuật toán, kỹ thuật hai con trỏ (Two Pointers) là một trong số đó.

Hai con trỏ là một pattern trong đó hai con trỏ lặp qua cấu trúc dữ liệu cho đến khi một hoặc cả hai thỏa mãn điều kiện cần thiết.

Đừng lo; “kỹ thuật hai con trỏ” có một bộ khái niệm hạn chế. Hơn nữa, đây là một kỹ thuật đơn giản và hiệu quả, khi được sử dụng đúng cách sẽ mang lại hiệu quả kỳ diệu.

Kết quả là, rất nhiều cuộc phỏng vấn có xu hướng hơi thiên về các câu hỏi sử dụng kỹ thuật này. Trong bài viết này, chúng ta sẽ xem xét các khái niệm cơ bản và cung cấp các ví dụ khác nhau để bạn biết khi nào và làm thế nào để áp dụng chiến lược hai con trỏ.

Cách tiếp cận hai con trỏ chính xác như những gì nó nghe. Chúng tôi sử dụng hai con trỏ để hoàn thành một nhiệm vụ nhất định.

Con trỏ là gì?

Một con trỏ (pointer) là một tham chiếu đến một đối tượng. Đối tượng đó lưu trữ một địa chỉ bộ nhớ có giá trị khác nằm trong bộ nhớ máy tính hoặc trong một số trường hợp là bộ nhớ của phần cứng máy tính được ánh xạ. Nói một cách đơn giản hơn – một biến lưu trữ địa chỉ của một mảng cũng là một con trỏ. Ví dụ, chúng ta đã tính kích thước của con trỏ trong chương trình C.

Đặt câu hỏi làm thế nào các kỹ thuật con trỏ và hai con trỏ có thể so sánh được?

Con trỏ lưu trữ địa chỉ của các đối tượng và chúng ta sẽ sử dụng thực tế này để trỏ đến các đối tượng khác nhau bằng cách sử dụng các biến trong kỹ thuật hai con trỏ. Vì vậy, trong trường hợp này, chúng còn được gọi là con trỏ.

Kỹ thuật hai con trỏ không gì khác hơn là tối ưu hóa thông minh các kỹ thuật vũ phu cụ thể. Nó làm giảm độ phức tạp về thời gian bằng cách sử dụng một số loại thứ tự thay vì nhất thiết phải sắp xếp dữ liệu.

Làm thế nào để sử dụng kỹ thuật hai con trỏ?

Trước khi chúng ta bắt đầu, hãy nhớ rằng con trỏ trong kỹ thuật này đại diện cho chỉ mục hoặc thuộc tính lặp, chẳng hạn như nút tiếp theo.

Hãy bắt đầu với một số ví dụ nổi tiếng nhất, có thể được giải quyết một cách tối ưu bằng cách sử dụng kỹ thuật hai con trỏ:

Ví dụ 1: Cho mảng A đã sắp xếp (sắp xếp theo thứ tự tăng dần) và một mục tiêu là số nguyên, tìm xem có tồn tại 2 số nguyên A[i] và A[j] sao cho A[i] + A[j] = mục tiêu, trong đó i !=j.

Đối với một mảng A đã cho, giả sử giá trị đích = 6