Kỹ thuật Two Pointers: "Hack" tốc độ vòng lặp từ O(n²) xuống O(n)

Trong thế giới Cấu trúc dữ liệu & Thuật toán (DSA), nỗi ám ảnh lớn nhất của lập trình viên là Time Limit Exceeded (Vượt quá thời gian chạy). Nguyên nhân thường đến từ việc lạm dụng vòng lặp lồng nhau (Nested Loops), khiến độ phức tạp thời gian vọt lên mức $O(n^2)$ hoặc tệ hơn.

Kỹ thuật Two Pointers (Hai con trỏ) ra đời như một liều thuốc giải độc cho vấn đề này. Nó cho phép bạn duyệt qua một mảng (hoặc chuỗi) bằng hai biến chỉ mục cùng lúc, giúp loại bỏ hoàn toàn vòng lặp thừa và kéo độ phức tạp xuống chỉ còn $O(n)$.

1. Nỗi đau của thuật toán Brute Force (Vét cạn)

Hãy tưởng tượng bạn nhận được một bài toán kinh điển: Two Sum II.

Cho một mảng các số nguyên đã được sắp xếp tăng dần (ví dụ: [2, 7, 11, 15]) và một số target = 9. Hãy tìm 2 số trong mảng cộng lại bằng target.

Cách "ngây thơ" nhất mà ai cũng nghĩ đến đầu tiên là dùng 2 vòng lặp for lồng nhau: Lấy số đầu tiên, rồi cộng thử với từng số phía sau nó.

function twoSumBruteForce(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === target) return [arr[i], arr[j]];
    }
  }
  return [];
}

Cách này chạy đúng, nhưng nếu mảng của bạn có 1.000.000 phần tử, vòng lặp lồng nhau sẽ phải thực hiện khoảng 1.000 tỷ phép tính. Trình duyệt của bạn sẽ lập tức treo cứng! Đây là lúc Two Pointers thể hiện sự thượng đẳng.

2. Mô hình 1: Hai con trỏ ngược chiều (Đối đầu)

Đây là mô hình phổ biến nhất, thường áp dụng cho các mảng đã được sắp xếp.

Tư duy cốt lõi:

Thay vì duyệt mò mẫm, ta đặt một con trỏ ở đầu mảng (left) và một con trỏ ở cuối mảng (right).

Bởi vì mảng đã được sắp xếp, ta có quy luật vàng sau:

• Nếu tổng của hai phần tử arr[left] + arr[right] lớn hơn target: Chứng tỏ số bên phải đang quá lớn. Ta phải giảm giá trị tổng xuống bằng cách dịch con trỏ right lùi về bên trái (right--).

• Nếu tổng nhỏ hơn target: Chứng tỏ số bên trái quá nhỏ. Ta tăng giá trị tổng lên bằng cách dịch con trỏ left sang phải (left++).

• Nếu bằng target: Ta tìm thấy đáp án!

Triển khai code:

function twoSumTwoPointers(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  // Chạy vòng lặp chừng nào hai con trỏ chưa đụng nhau
  while (left < right) {
    const currentSum = arr[left] + arr[right];

    if (currentSum === target) {
      return [arr[left], arr[right]]; // Đã tìm thấy
    } 
    else if (currentSum > target) {
      right--; // Tổng lớn quá, thu nhỏ lại
    } 
    else {
      left++;  // Tổng nhỏ quá, phóng to lên
    }
  }
  
  return []; // Không tìm thấy
}

Tại sao nó ảo diệu?

Mỗi bước lặp, ta chắc chắn loại bỏ được một phần tử không phù hợp. Hai con trỏ tiến về nhau và gặp nhau ở giữa. Ta chỉ đi qua mỗi phần tử đúng 1 lần. Số phép tính tối đa cho 1 triệu phần tử giờ đây chỉ là 1 triệu phép tính (Độ phức tạp $O(n)$). Nhanh gấp một triệu lần cách cũ!

3. Mô hình 2: Hai con trỏ cùng chiều (Nhanh và Chậm)

Mô hình này (hay còn gọi là Fast & Slow Pointers) thường dùng khi bạn cần sàng lọc dữ liệu, sửa đổi mảng trực tiếp (in-place) hoặc phát hiện chu trình.

Bài toán ví dụ: Move Zeroes

Cho một mảng [0, 1, 0, 3, 12]. Hãy đẩy toàn bộ số 0 về cuối mảng, nhưng vẫn phải giữ nguyên thứ tự của các số khác. Bắt buộc sửa trực tiếp trên mảng gốc (Không tốn thêm bộ nhớ $O(1)$).

Tư duy cốt lõi:

Ta dùng hai con trỏ xuất phát cùng một vạch:

• Con trỏ chậm (slow): Chỉ tay vào vị trí "trống" tiếp theo sẵn sàng để chứa một số khác 0.

• Con trỏ nhanh (fast): Chạy hùng hục lên phía trước để dò tìm các số khác 0.

Khi con trỏ nhanh tìm thấy một số khác 0, nó lập tức "ném" số đó về vị trí của con trỏ chậm, rồi cả hai cùng tiến lên một bước.

Triển khai code:

function moveZeroes(nums) {
  let slow = 0;

  // fast chạy trước để tìm các số khác 0
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      // Đổi chỗ (Swap) phần tử tại slow và fast
      let temp = nums[slow];
      nums[slow] = nums[fast];
      nums[fast] = temp;
      
      // slow nhích lên 1 bước để đón số tiếp theo
      slow++;
    }
  }
  return nums;
}

Kết quả: Chỉ với 1 vòng lặp for, mảng được sắp xếp lại hoàn hảo mà không cần phải tốn RAM tạo ra một cái mảng tạm [] nào cả!

4. Dấu hiệu nhận biết khi nào nên dùng Two Pointers

Khi đi phỏng vấn thuật toán, làm sao để "đánh hơi" thấy bài toán này cần dùng Two Pointers? Dưới đây là các "red flag" (dấu hiệu) cực kỳ rõ ràng:

• Mảng đã được sắp xếp (Sorted Array): Đây là dấu hiệu mạnh nhất. Hễ thấy từ "sorted", hãy nghĩ ngay đến Two Pointers hoặc Binary Search.

• Tìm cặp/bộ ba (Pairs/Triplets): Các bài toán tìm 2 số, 3 số có tổng/hiệu thỏa mãn điều kiện.

• Xử lý chuỗi đối xứng (Palindrome): Kiểm tra xem chữ "RACECAR" viết ngược lại có giống viết xuôi không (Một con trỏ ở đầu, một ở cuối, chạy vào giữa kiểm tra từng ký tự).

• Yêu cầu In-place (Độ phức tạp không gian O(1)): Đề bài cấm bạn xài thêm mảng phụ để lưu trữ tạm thời, ép bạn phải thao tác trực tiếp trên mảng gốc.

5. Lời kết

Two Pointers không hẳn là một thuật toán phức tạp cao siêu, nó giống một Mindset (Tư duy) hơn. Việc làm chủ được cách điều khiển nhiều con trỏ cùng lúc chứng tỏ bạn đã hiểu rất sâu về cách quản lý bộ nhớ và luồng dữ liệu (Control Flow).

Lần tới, trước khi đặt bút viết vòng lặp for thứ hai lồng vào bên trong, hãy tự hỏi: "Liệu mình có thể đưa một con trỏ chạy từ cuối mảng lên không?". Câu trả lời có thể sẽ tiết kiệm cho hệ thống của bạn hàng triệu phép tính thừa thãi đấy!