Kỹ thuật two pointers là gì?

Question

Accepted Answer

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

```python
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)       # tìm thấy cặp
        elif s < target:
            lo += 1               # cần tổng lớn hơn
        else:
            hi -= 1               # cần tổng nhỏ hơn
    return None

two_sum_sorted([1, 3, 4, 6, 9], 10)   # -> (1, 3) cho 4 + 6
```

## Độ phức tạp

- **Thời gian:** O(n). **Bộ nhớ:** O(1).

## Khi nào dùng / những cạm bẫy

Rất hợp với **mảng đã sắp xếp**, kiểm tra palindrome, đảo ngược, và loại bỏ phần tử trùng lặp tại chỗ. Mảng thường phải được sắp xếp cho biến thể hai con trỏ hội tụ. Hãy cẩn thận với biên của con trỏ và điều kiện vòng lặp (`lo < hi`).

## Tại sao điều này quan trọng

Two pointers là một trong những mô thức phỏng vấn có đòn bẩy cao nhất: nó thu gọn các vòng lặp lồng nhau thành một lần quét tuyến tính gọn gàng.

Nó dạy bạn khai thác cấu trúc (như tính đã sắp xếp) thay vì vét cạn.

Cùng ý tưởng này vận hành cho việc trộn (merge), phân hoạch (partition), và bước trộn của merge sort.