I. Tổng Quan về Kỹ Thuật Two Pointers

Kỹ thuật hai con trỏ (Two Pointers) là một phương pháp tối ưu trong lập trình, đặc biệt trong lĩnh vực lập trình thi đấu. Kỹ thuật này cho phép tiết kiệm cả không gian lưu trữ và thời gian thực thi của thuật toán, đặc biệt là khi làm việc với các bài toán liên quan đến mảng hoặc chuỗi.

Kỹ thuật hai con trỏ sử dụng hai biến để kiểm soát hai vị trí khác nhau trong mảng hoặc chuỗi. Điểm đặc biệt là một biến không bao giờ vượt quá biến còn lại. Dưới đây là ba dạng chính của kỹ thuật Two Pointers:

1. Slow And Fast: Một con trỏ chạy chậm, trong khi con trỏ còn lại chạy nhanh.
2. Left & Right Boundary: Hai con trỏ di chuyển ngược chiều nhau.
3. Sliding Windows: Hai con trỏ di chuyển với cùng tốc độ theo một hướng.

II. Dạng Bài Tập Slow And Fast

1. Giải Thuật Tổng Quát

Trong dạng bài này, ta luôn có một con trỏ di chuyển chậm (slow) và một con trỏ di chuyển nhanh (fast). Con trỏ chậm chỉ tiến lên khi nó thỏa mãn một điều kiện nào đó.

Giả thuyết mã giả:

void slow_and_fast()
{
    pointer_1 = {chỉ số đầu};
    for (pointer_2 = {chỉ số đầu}; pointer_2 <= {chỉ số cuối}; ++pointer_2)
    {
        if ({pointer_1 thỏa mãn điều kiện})
            {Tăng pointer_1};
        {Xử lý logic};
    }
}

2. Bài Tập Ví Dụ

Bài Tập 1: Cho mảng số nguyên đã được sắp xếp tăng dần. Yêu cầu: loại bỏ các phần tử trùng lặp và đưa ra độ dài của dãy mới.

Giải Pháp: Sử dụng hai con trỏ slow và fast để quét qua mảng. Con trỏ fast duyệt qua mọi phần tử, trong khi con trỏ slow lưu giữ phần tử khác nhau. Độ phức tạp là O(n).

Bài Tập 2: Tìm dãy con liên tiếp có độ hoàn hảo lớn nhất với tổng không nhỏ hơn K. Sử dụng mảng tổng tiền tố và áp dụng kỹ thuật two pointers để tìm dãy phù hợp.

III. Dạng Left & Right Boundary

1. Giải Thuật Tổng Quát

Sử dụng hai con trỏ, một ở đầu và một ở cuối dãy. Hai con trỏ liên tục di chuyển đến khi gặp nhau.

Giả thuyết mã giả:

void left_right_boundary(seq)
{
    left = 0, right = seq.size() - 1;
    while (left < right)
    {
        if ({left thỏa mãn điều kiện})
            left += 1;
        if ({right thỏa mãn điều kiện})
            right -= 1;
        {Xử lý logic};
    }
}

IV. Dạng Sliding Window

1. Giải Thuật Tổng Quát

Kỹ thuật Sliding Window sử dụng hai con trỏ liên tục để cập nhật kết quả dựa trên đoạn con mà chúng kiểm soát.

Giả thuyết mã giả:

void sliding_window(seq)
{
    start = 0, end = start + window_size - 1;
    while (end < seq.size())
    {
        {Tính toán kết quả của window hiện tại};
        {Dịch chuyển window ra phía sau};
        {Cập nhật kết quả tốt nhất};
    }
}

V. Tài Liệu Tham Khảo

Các bạn có thể tham khảo thêm tài liệu trên trang Pluralsight và Baeldung để hiểu sâu hơn về kỹ thuật Two Pointers.
source: viblo