Giải bài toán hai con trỏ (Two Pointers) kinh điển trong LeetCode: Tìm cặp số có tổng bằng Target

Kỹ thuật tối ưu thuật toán phổ biến nhất trong các buổi phỏng vấn#

Kỹ thuật Hai con trỏ (Two Pointers) là một trong những vũ khí mạnh mẽ nhất giúp giảm độ phức tạp thời gian từ bậc hai $O(N^2)$ xuống tuyến tính $O(N)$ cho các bài toán xử lý mảng và chuỗi.

Hãy cùng phân tích bài toán kinh điển: Two Sum II - Input Array Is Sorted (LeetCode 167).

Đề bài#

Cho một mảng số nguyên numbers đã được sắp xếp theo thứ tự tăng dần và một số nguyên target. Hãy tìm chỉ số của hai số sao cho tổng của chúng đúng bằng target. Yêu cầu: Không sử dụng thêm mảng phụ, độ phức tạp bộ nhớ (Space Complexity) phải là $O(1)$.

Phân tích hướng giải quyết#

Cách 1: Brute Force (Duyệt cạn)#

Dùng 2 vòng lặp lồng nhau thử mọi cặp số:

• Độ phức tạp: $O(N^2)$ thời gian. Sẽ bị lỗi Time Limit Exceeded (TLE) nếu mảng có 100.000 phần tử.

Cách 2: Kỹ thuật Hai con trỏ từ 2 đầu (Optimal $O(N)$)#

Đặt con trỏ left ở đầu mảng (chỉ số 0 - phần tử nhỏ nhất) và con trỏ right ở cuối mảng (chỉ số $N-1$ - phần tử lớn nhất):

export function twoSum(numbers: number[], target: number): number[] {
  let left = 0;
  let right = numbers.length - 1;

  while (left < right) {
    const currentSum = numbers[left] + numbers[right];

    if (currentSum === target) {
      return [left + 1, right + 1]; // Đề bài yêu cầu index từ 1
    } else if (currentSum < target) {
      // Tổng quá nhỏ -> Cần tăng tổng -> Tịnh tiến con trỏ trái sang phải!
      left++;
    } else {
      // Tổng quá lớn -> Cần giảm tổng -> Tịnh tiến con trỏ phải sang trái!
      right--;
    }
  }

  return [];
}

Vì sao giải pháp này tối ưu tuyệt đối?#

• Thời gian: Mỗi bước vòng lặp, một trong hai con trỏ dịch chuyển 1 bước. Tổng số bước tối đa là $N$. Độ phức tạp là $O(N)$!
• Bộ nhớ: Chỉ dùng 2 biến con trỏ số nguyên $\rightarrow$ $O(1)$ auxiliary space.

Góc thảo luận#

Bạn đã áp dụng kỹ thuật Two Pointers cho các bài toán nào khác chưa? Ví dụ như bài toán Tìm chuỗi Palindrome hoặc Bài toán 3Sum?

Xem thêm nội dung liên quan:

• Bộ 2.916 câu trắc nghiệm Thuật toán
• Lộ trình ôn luyện LeetCode phỏng vấn