Kỹ thuật two pointers dùng hai chỉ số di chuyển qua một dãy để giải bài toán chỉ trong một lần duyệt — biến nhiều giải pháp vét cạn O(n²) thành O(n).
Ý tưởng
Giữ hai con trỏ (thường ở hai đầu, hoặc một chậm một nhanh) và di chuyển chúng dựa trên một điều kiện, thu hẹp khối lượng công việc mà không cần quét lại.
Ví dụ: tìm cặp có tổng bằng giá trị mục tiêu trong mảng đã sắp xếp
():
lo, hi = , (arr) -
lo < hi:
s = arr[lo] + arr[hi]
s == target:
(lo, hi)
s < target:
lo +=
:
hi -=
two_sum_sorted([, , , , ], )
