Cấu trúc dữ liệu và Giải thuật Bài 21: Kỹ thuật Hai con trỏ (Two Pointers): Cùng chiều và Ngược chiều.

Trong các dự án phát triển hệ thống backend, đôi khi bạn sẽ phải đối mặt với những bài toán tìm kiếm cặp phần tử hoặc sàng lọc dữ liệu trực tiếp trên một mảng khổng lồ. Cách tiếp cận ngây thơ (vòng lặp lồng nhau) luôn mang lại độ phức tạp $O(n^2)$ . Kỹ thuật Hai con trỏ (Two Pointers) ra đời như một thủ thuật toán học để đè bẹp $O(n^2)$ xuống chỉ còn $O(n)$ , đồng thời giữ mức tiêu thụ bộ nhớ ở $O(1)$ .

Bản chất của kỹ thuật này cực kỳ đơn giản: Thay vì dùng một biến i chạy từ đầu đến cuối mảng, chúng ta thả hai biến chỉ mục (index) chạy đồng thời. Tùy thuộc vào quỹ đạo di chuyển, chúng được chia thành hai trường phái: Ngược chiều và Cùng chiều.

1. Hai con trỏ ngược chiều (Opposite-Directional Pointers)

Kỹ thuật này là "vũ khí hủy diệt" dành riêng cho các mảng đã được sắp xếp (Sorted Arrays).

Cơ chế hoạt động:

Con trỏ thứ nhất (left) đặt ở đầu mảng (index 0).
Con trỏ thứ hai (right) đặt ở cuối mảng (index $N - 1$ ).
Hai con trỏ từ từ tiến lại gần nhau và hội tụ ở giữa. Tùy thuộc vào tổng hoặc điều kiện của hai phần tử tại left và right, chúng ta quyết định di chuyển con trỏ nào.

Bài toán kinh điển: Two Sum II (Tìm 2 số có tổng bằng Target trên mảng đã sắp xếp)

Cho mảng A = [2, 7, 11, 15] và Target = 9.

Bước 1: left = 0 (giá trị 2), right = 3 (giá trị 15).
Bước 2: Tính tổng: $2 + 15 = 17$ .
Bước 3: Vì $17 > 9$ (tổng đang lớn hơn đích), chúng ta cần một tổng nhỏ hơn. Do mảng đã sắp xếp tăng dần, cách duy nhất để thu được giá trị nhỏ hơn là dịch con trỏ right sang trái (right--).
Bước 4: left = 0 (giá trị 2), right = 2 (giá trị 11). Tổng là $13 > 9$ . Tiếp tục giảm right--.
Bước 5: left = 0 (giá trị 2), right = 1 (giá trị 7). Tổng là $9 == Target$ . Dừng thuật toán.

// Cài đặt bằng Golang
func twoSumSorted(numbers []int, target int) []int {
    left := 0
    right := len(numbers) - 1
    
    for left < right {
        sum := numbers[left] + numbers[right]
        
        if sum == target {
            return []int{left, right}
        } else if sum < target {
            left++  // Cần tổng lớn hơn -> nhích con trỏ trái lên
        } else {
            right-- // Cần tổng nhỏ hơn -> lùi con trỏ phải xuống
        }
    }
    
    return []int{} // Không tìm thấy
}

Độ phức tạp: Thời gian $O(n)$ vì mỗi phần tử chỉ bị quét đúng một lần. Không gian $O(1)$ . Ngoài ra, kỹ thuật này còn được áp dụng để đảo ngược mảng hoặc kiểm tra chuỗi đối xứng (Palindrome).

2. Hai con trỏ cùng chiều (Same-Directional Pointers / Fast & Slow Pointers)

Kỹ thuật này được sử dụng khi bài toán yêu cầu sàng lọc, ghi đè hoặc xóa bỏ dữ liệu ngay trên mảng gốc (In-place modification) mà không được cấp phát thêm mảng mới để tiết kiệm RAM.

Cơ chế hoạt động:

Cả hai con trỏ đều xuất phát từ đầu mảng (hoặc cùng một vị trí).
Con trỏ nhanh (Fast pointer): Đóng vai trò là người đi thám hiểm. Nó duyệt qua từng phần tử của mảng để kiểm tra điều kiện.
Con trỏ chậm (Slow pointer): Đóng vai trò là người giữ sổ. Nó chỉ nhích lên khi con trỏ nhanh tìm thấy một phần tử hợp lệ cần được giữ lại.

Bài toán kinh điển: Chuyển toàn bộ số 0 về cuối mảng (Move Zeroes)

Cho mảng A = [0, 1, 0, 3, 12]. Yêu cầu đẩy hết số 0 về cuối, giữ nguyên thứ tự các số khác, không dùng mảng phụ.

Khởi tạo slow = 0.
Dùng fast chạy từ 0 đến 4.
Bất cứ khi nào A[fast] khác 0, ta đổi chỗ (swap) A[fast] và A[slow], sau đó tăng slow lên 1.

Quá trình chạy:

fast = 0 (giá trị 0). Bỏ qua. slow = 0.
fast = 1 (giá trị 1). Khác 0. Đổi chỗ A[0] và A[1]. Mảng thành [1, 0, 0, 3, 12]. slow tăng lên 1.
fast = 2 (giá trị 0). Bỏ qua. slow = 1.
fast = 3 (giá trị 3). Khác 0. Đổi chỗ A[1] và A[3]. Mảng thành [1, 3, 0, 0, 12]. slow tăng lên 2.
fast = 4 (giá trị 12). Khác 0. Đổi chỗ A[2] và A[4]. Mảng thành [1, 3, 12, 0, 0].

func moveZeroes(nums []int) {
    slow := 0
    
    // Con trỏ fast quét toàn bộ mảng
    for fast := 0; fast < len(nums); fast++ {
        // Nếu gặp số khác 0, hoán đổi với vị trí slow và nhích slow lên
        if nums[fast] != 0 {
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow++
        }
    }
}

Độ phức tạp: Thời gian $O(n)$ do con trỏ fast đi đúng một vòng. Không gian $O(1)$ do mọi thao tác hoán đổi đều làm trực tiếp trên mảng hiện tại.

3. Dấu hiệu nhận biết bài toán cần dùng Hai con trỏ

Để phản xạ nhanh trong các buổi phỏng vấn hoặc tối ưu module hệ thống, hãy dùng kỹ thuật này khi thấy các "từ khóa" sau trong yêu cầu:

"Sorted array" (Mảng đã sắp xếp) + Tìm cặp/bộ ba số: Dấu hiệu tuyệt đối cho việc dùng Hai con trỏ ngược chiều. Bài toán kinh điển là 3Sum.
"In-place" (Ngay trên mảng gốc) + Xóa trùng lặp/Di chuyển phần tử: Dấu hiệu cho Hai con trỏ cùng chiều (Fast & Slow).
So sánh 2 mảng/chuỗi cùng lúc: Ví dụ bài toán trộn hai mảng đã sắp xếp (Merge hai mảng). Bạn đặt một con trỏ ở mảng A, một con trỏ ở mảng B và tiến dần về đích.

Kỹ thuật Hai con trỏ giải quyết rất tốt các bài toán tĩnh hoặc có chiều dài di chuyển không cố định. Tuy nhiên, nếu bài toán yêu cầu tìm kiếm các đặc tính trên một "khối dữ liệu" có kích thước nhất định trượt dọc theo mảng (ví dụ: Tổng doanh thu cao nhất trong đúng 3 ngày liên tiếp), ta sẽ cần đến một biến thể nâng cấp của Hai con trỏ.

cấu trúc dữ liệu

1. Hai con trỏ ngược chiều (Opposite-Directional Pointers)

2. Hai con trỏ cùng chiều (Same-Directional Pointers / Fast & Slow Pointers)

3. Dấu hiệu nhận biết bài toán cần dùng Hai con trỏ

Mục lục