Quét mảng đã sắp xếp từ hai đầuTương tác

Hai con trỏ — Two-Pointer

4 bàidễ (2)trung bình (2)O(n)

Hai con trỏ là kỹ thuật đặt hai chỉ số chạy trên cùng một mảng hoặc chuỗi — ngược chiều (từ hai đầu dồn vào giữa) hoặc đồng chiều (nhanh và chậm) — để hạ độ phức tạp từ O(n²) xuống O(n).

Kỹ thuật này phát huy nhất khi dữ liệu đã sắp xếp: mỗi bước ta quyết định dịch con trỏ nào dựa trên một phép so sánh, nhờ vậy không tốn bộ nhớ phụ. Cái khó là chọn đúng điều kiện dịch chuyển để vừa nhanh vừa không bỏ sót nghiệm.

Hình dung một dãy số đã xếp tăng dần với một ngón tay ở mỗi đầu: tổng hai đầu lớn hơn đích thì ngón phải lùi vào cho nhỏ lại, nhỏ hơn thì ngón trái tiến tới cho lớn lên — nhờ dãy đã sắp xếp, mỗi bước chỉ cần một phép so là biết nên dịch bên nào, khỏi thử mọi cặp.

Dấu hiệu nhận biết

Gặp những từ khoá này trong đề → nghĩ ngay đến Hai con trỏ

Từ khoá trong đề	Tại sao gợi đến chủ đề này
mảng đã sắp xếp	Two-pointer hiệu quả nhất trên sorted
tìm cặp / tổng = target	Hội tụ về giữa từ 2 đầu
palindrome	Pointer 2 đầu so sánh dần
loại trùng tại chỗ	Slow + fast pointer trên cùng mảng

Khi nào dùng

4 tình huống điển hình cần nghĩ đến chủ đề này

Mảng đã được sắp xếp

Cần tìm cặp/bộ ba thoả điều kiện tổng

Cần đảo ngược, so sánh đối xứng (palindrome)

Cần loại trùng tại chỗ

Khi nào KHÔNG dùng

3 tình huống chủ đề này không phù hợp — biết để tránh overuse

Mảng KHÔNG sorted và không cần sorted: Hash Map thường nhanh hơn về code

Cần truy vấn vị trí ngẫu nhiên: Two-Pointer chỉ quét tuyến tính, không phù hợp

Bài đếm subarray rời rạc theo điều kiện tổng: Prefix Sum + Hash Map phù hợp hơn

Hình minh hoạ

Chỉnh dữ liệu rồi bấm Phát để xem từng bước.

left = 0right = 5sum = 16target = 9

Khởi tạo: left=0, right=5, tổng = 16

Bước 1 / 5

Tốc độ:

// Hai con trỏ trên mảng đã sắp xếp tìm cặp tổng = target
let left = 0, right = nums.length - 1
while (left < right) {
  if (nums[left] + nums[right] === target) return [left, right]
  if (nums[left] + nums[right] < target) left++
  else right--
}
return null

Mảng (tự sắp xếp): Mục tiêu:

Code mẫu

Hầu hết bài cùng chủ đề dùng chung mẫu này — copy rồi điền phần logic riêng của bài.

typescript

function twoPointer(nums: T[]): R {
  let left = 0
  let right = nums.length - 1

  while (left < right) {
    if (condition(nums[left], nums[right])) {
      return result(left, right)
    }
    if (shouldMoveLeft(nums[left], nums[right])) {
      left++
    } else {
      right--
    }
  }
  return notFound
}

Recap

Tổng hợp nhanh — đọc lại trước phỏng vấn

Điểm chính

Khởi tạo left=0, right=length-1 (ngược hướng) hoặc cả 2 ở đầu (đồng hướng)
So sánh điều kiện tại 2 con trỏ rồi quyết định di chuyển
Vòng lặp dừng khi left >= right (ngược hướng)

Lỗi thường gặp

Quên rằng mảng phải sorted (nếu không sort thì cần Hash Map)
Off-by-one ở điều kiện left < right vs left <= right
Khi gặp duplicate, quên skip thêm

Độ phức tạp

Time O(n), Space O(1)

Bài luyện theo chủ đề này

Phân theo độ khó — luyện tuần tự cho chắc tay

Dễ 2 bài

Dễ 15p

Hai Tổng Trên Mảng Sắp Xếp

Dễ 12p

Xác Nhận Palindrome

Trung bình 2 bài

Trung bình 20p

Bể Chứa Nước Nhiều Nhất

Trung bình 30p

Ba Tổng Bằng Không

Tham khảo thêm

Từ khoá trong đề

Tại sao gợi đến chủ đề này

mảng đã sắp xếp

Two-pointer hiệu quả nhất trên sorted

tìm cặp / tổng = target

Hội tụ về giữa từ 2 đầu

palindrome

Pointer 2 đầu so sánh dần

loại trùng tại chỗ

Slow + fast pointer trên cùng mảng

// Hai con trỏ trên mảng đã sắp xếp tìm cặp tổng = target

let left = 0, right = nums.length - 1

while (left < right) {

if (nums[left] + nums[right] === target) return [left, right]

if (nums[left] + nums[right] < target) left++

else right--

}

return null

function twoPointer(nums: T[]): R { let left = 0 let right = nums.length - 1 while (left < right) { if (condition(nums[left], nums[right])) { return result(left, right) } if (shouldMoveLeft(nums[left], nums[right])) { left++ } else { right-- } } return notFound }