Hai Con Trỏ (Two Sum Pointers)

Kỹ Thuật Hai Con Trỏ (Two Pointers)

Tìm cặp số có tổng bằng Target trên mảng đã sắp xếp trong độ phức tạp O(N).

-5

Target

-5

-2

Chốt 2 con trỏ L (Left) và R (Right) ở hai đầu mảng đã sắp xếp.

Tốc Độ

Thống Kê

Bước

0 / 12

Mục Tiêu

Tiến Độ

Thay vì sử dụng 2 vòng lặp (Brute-force) nhức nách tốn O(N²), ta dùng kẹp chả 2 đầu.

Nếu SUM < Target:

L++ (Trượt trái sang phải để tăng tổng vì mảng đã sort sẵn).

Nếu SUM > Target:

R-- (Trượt phải sang trái để làm giảm tổng).

Quy luật bảo toàn bù trừ này giúp ta rà soát toàn mảng chỉ trong 1 lần quét O(N) duy nhất.