Wiki › Thuật toán › Two Pointers

Two Pointers

huunguyen Updated Tháng sáu 1, 2026

Two Pointers (hai con trỏ) là kỹ thuật dùng hai chỉ số $l$ và $r$ cùng quét qua mảng/xâu, nhờ đó xử lý nhiều bài toán tìm đoạn con hoặc tìm cặp trong $O (N)$ thay vì $O (N^{2})$ như duyệt trâu.

Ý tưởng cốt lõi

Duyệt trâu thử mọi cặp $(l, r)$ mất $O (N^{2})$ vì mỗi khi $r$ tăng ta lại dò $l$ từ đầu. Two Pointers nhanh hơn nhờ một quan sát: khi $r$ đã đi qua, con trỏ $l$ không bao giờ cần lùi lại. Điều này chỉ đúng khi bài toán có tính đơn điệu (monotone):

Với cửa sổ trượt cùng chiều: khi mở rộng cửa sổ sang phải (tăng $r$ ) làm trạng thái "xấu đi" theo một chiều (tổng tăng, số phần tử phân biệt tăng...), thì để khôi phục điều kiện ta chỉ có thể co biên trái sang phải — không bao giờ phải kéo $l$ ngược lại.
Với hai con trỏ ngược chiều trên mảng đã sắp xếp: nếu $a [l] + a [r]$ quá lớn thì mọi cặp dùng $r$ với chỉ số $\geq l$ cũng quá lớn, nên giảm $r$ là an toàn; ngược lại thì tăng $l$ .

Chính vì mỗi con trỏ chỉ đi một chiều và không quay lại, tổng số bước bị chặn bởi $O (N)$ .

Dạng 1: Cửa sổ trượt (Sliding Window — cùng chiều)

$l$ và $r$ cùng tiến sang phải, duy trì cửa sổ $[l, r]$ luôn thỏa một điều kiện.

Ví dụ chạy tay

Tìm đoạn con dài nhất có tổng $\leq K$ với $a = [2, 1, 5, 1, 3, 2]$ , $K = 7$ . Quy ước: vùng trong ngoặc [ ] là cửa sổ hiện tại, sum là tổng cửa sổ.

a = [ 2  1  5  1  3  2 ]
      0  1  2  3  4  5     (chỉ số)

r=0:  [2]            sum=2  ≤7  → dài 1
r=1:  [2 1]          sum=3  ≤7  → dài 2
r=2:  [2 1 5]        sum=8  >7  → co trái: bỏ a[0]=2
       (1 5)         sum=6  ≤7  → dài 2
r=3:   [1 5 1]       sum=7  ≤7  → dài 3   ← tốt nhất tới giờ
r=4:   [1 5 1 3]     sum=10 >7  → co trái: bỏ a[1]=1 (sum=9), bỏ a[2]=5 (sum=4)
            (1 3)    sum=4  ≤7  → dài 2
r=5:        (1 3 2)  sum=6  ≤7  → dài 3

Đáp án: 3  (đoạn [1,5,1] hoặc [1,3,2])

Để ý: biên trái $l$ chỉ tiến từ 0 → 3 trong suốt quá trình, không bao giờ lùi. Đó là lý do thuật toán là $O (N)$ .

Cài đặt

// Đoạn con dài nhất có tổng <= K (mọi phần tử > 0)
int max_len(vector<int>& a, int K) {
    int n = a.size(), ans = 0;
    long long sum = 0;
    for (int l = 0, r = 0; r < n; r++) {
        sum += a[r];               // mở rộng cửa sổ sang phải
        while (sum > K) sum -= a[l++];  // co biên trái cho tới khi hợp lệ
        ans = max(ans, r - l + 1);
    }
    return ans;
}

// Đoạn con ngắn nhất có tổng >= K (mọi phần tử > 0)
int min_len(vector<int>& a, int K) {
    int n = a.size(), ans = n + 1;
    long long sum = 0;
    for (int l = 0, r = 0; r < n; r++) {
        sum += a[r];
        while (sum >= K) {
            ans = min(ans, r - l + 1);
            sum -= a[l++];
        }
    }
    return ans == n + 1 ? -1 : ans;
}

Dạng 2: Ngược chiều (Two Sum trên mảng đã sắp xếp)

$l$ bắt đầu từ trái, $r$ từ phải, cùng tiến vào giữa. Dùng để tìm cặp $(i, j)$ thỏa điều kiện về tổng trên mảng đã sắp xếp.

Ví dụ chạy tay

Tìm cặp có tổng $= 8$ trong $a = [1, 2, 4, 5, 7]$ (đã sắp xếp):

a = [ 1  2  4  5  7 ]
      l           r       s = 1+7 = 8  = 8  → tìm thấy! (1,7)
      l        r          (nếu cần đếm tiếp) s = 1+5 = 6  < 8 → l++
         l     r          s = 2+5 = 7  < 8 → l++
            l  r          s = 4+5 = 9  > 8 → r--
            l  r          l==r → dừng

Khi $s < 8$ ta tăng $l$ (cần tổng lớn hơn); khi $s > 8$ ta giảm $r$ (cần tổng nhỏ hơn). Vì mảng đã sắp xếp, mỗi quyết định loại bỏ chắc chắn một đầu mà không bỏ sót nghiệm.

Cài đặt

// Kiểm tra có cặp nào tổng = target không (mảng đã sort)
bool has_pair(vector<int>& a, int target) {
    int l = 0, r = a.size() - 1;
    while (l < r) {
        int s = a[l] + a[r];
        if (s == target) return true;
        else if (s < target) l++;   // cần tổng lớn hơn
        else r--;                    // cần tổng nhỏ hơn
    }
    return false;
}

Dạng 3: Hai con trỏ trên hai mảng

Mỗi con trỏ chạy trên một mảng đã sắp xếp; thường dùng để đếm/ghép theo điều kiện.

// Đếm cặp (a[i], b[j]) với a[i] + b[j] <= K (cả hai đã sort tăng dần)
long long count_pairs_two_arrays(vector<int>& a, vector<int>& b, int K) {
    long long cnt = 0;
    int j = b.size() - 1;
    for (int i = 0; i < (int)a.size(); i++) {
        // a[i] tăng dần ⇒ ngưỡng b[j] hợp lệ chỉ giảm ⇒ j chỉ đi sang trái
        while (j >= 0 && a[i] + b[j] > K) j--;
        cnt += j + 1;   // mọi b[0..j] đều ghép được với a[i]
    }
    return cnt;
}

Một ví dụ kinh điển: đoạn con không lặp ký tự

Tìm độ dài đoạn con dài nhất không có ký tự lặp — cửa sổ trượt với bộ đếm tần suất:

int longest_unique(const string& s) {
    int n = s.size(), ans = 0;
    unordered_map<char, int> cnt;
    for (int l = 0, r = 0; r < n; r++) {
        cnt[s[r]]++;
        while (cnt[s[r]] > 1) cnt[s[l++]]--;  // co trái tới khi s[r] hết lặp
        ans = max(ans, r - l + 1);
    }
    return ans;
}

Độ phức tạp


Thời gian	$O (N)$ — mỗi con trỏ $l, r$ chỉ tiến, mỗi phần tử được "vào" và "ra" cửa sổ đúng một lần, tổng $\leq 2 N$ bước. (Với Dạng 2 cần mảng đã sắp xếp thì cộng $O (N \log N)$ cho bước sort.)
Bộ nhớ	$O (1)$ ngoài mảng đầu vào (Dạng cửa sổ trượt với bộ đếm thì $O (Σ)$ với $Σ$ là số giá trị phân biệt).

Mấu chốt: vòng while bên trong không làm thuật toán thành $O (N^{2})$ , vì $l$ trên toàn bộ quá trình chỉ chạy tổng cộng $\leq N$ bước — đây là phân tích khấu hao (amortized).

⚠️ Lỗi thường gặp

Tràn số khi cộng dồn: tổng cửa sổ có thể vượt int. Dùng long long cho biến sum (như code trên), nhất là khi $a_{i}$ và $N$ lớn.
Dùng cửa sổ trượt khi có số âm/số 0: kỹ thuật co biên cho bài "tổng $\leq K$ " chỉ đúng khi mọi phần tử dương. Nếu có số âm, tổng không còn đơn điệu theo độ rộng cửa sổ ⇒ co trái không khôi phục được điều kiện. Khi đó cần tiền tố + cấu trúc khác (vd map, deque), không phải two pointers thuần.
Quên sắp xếp ở Dạng 2: two pointers ngược chiều đòi mảng đã sắp xếp. Quên sort sẽ cho kết quả sai mà không báo lỗi. Nếu bài cần giữ chỉ số gốc, hãy sort trên bản sao/chỉ số.
Đếm cặp trùng nhau bị sai: khi đếm số cặp tổng $= t a r g e t$ và có nhiều giá trị bằng nhau, nhảy l++; r--; một bước dễ đếm thiếu. Phải đếm số lượng phần tử bằng a[l] và bằng a[r] rồi nhân tổ hợp (xử lý riêng trường hợp a[l] == a[r]).
Off-by-one ở độ dài cửa sổ: độ dài đoạn $[l, r]$ là r - l + 1, không phải r - l.
Vòng while co biên vượt $r$ : với điều kiện chặt, $l$ có thể vượt $r$ làm cửa sổ rỗng. Đảm bảo bất biến l <= r + 1 và chỉ cập nhật đáp án khi cửa sổ hợp lệ.
l < r vs l <= r: Dạng 2 ghép cặp hai phần tử khác nhau dùng l < r; nếu cho phép dùng lại một phần tử (vd ghép với chính nó) mới dùng l <= r.

Khi nào dùng Two Pointers?

Mảng đã sắp xếp + tìm cặp/bộ thỏa điều kiện về tổng.
Tìm đoạn con tối ưu khi điều kiện có tính đơn điệu: mở rộng cửa sổ làm trạng thái thay đổi một chiều, cho phép biên trái chỉ tiến.
Thay thế brute force $O (N^{2})$ khi cửa sổ có thể co/giãn đơn điệu.

Bài tập luyện

Tổng Cửa Sổ Trượt (swsum) — (Amateur) khởi động: duy trì tổng của cửa sổ kích thước cố định, làm quen thao tác vào/ra phần tử.
Phòng Cho Thuê (apartments) — (Amateur) ghép cặp hai nhóm đã sắp xếp bằng hai con trỏ — kinh điển cho Dạng 3.
Tổng Hai Giá Trị (sum2vals) — (Amateur) Two Sum ngược chiều trên mảng đã sắp xếp (Dạng 2), nhớ giữ chỉ số gốc.
Giá Trị Phân Biệt Cửa Sổ Trượt (swdist) — (Amateur) cửa sổ trượt + bộ đếm tần suất, đúng mô-típ "đoạn con không lặp".
Tổng Mảng Con II (subsum2) — (Intermediate) đếm số đoạn con thỏa điều kiện tổng — luyện co/giãn cửa sổ với điều kiện đơn điệu.
Tổng Ba Giá Trị (sum3val) — (Intermediate) mở rộng Two Sum: cố định một phần tử rồi dùng hai con trỏ cho phần còn lại.