Kỹ thuật con trỏ (Two Pointers)

Kỹ thuật con trỏ là phương pháp sử dụng hai con trỏ di chuyển trên tập dữ liệu (mảng, danh sách liên kết...) nhằm tối ưu hóa quá trình tìm kiếm, so sánh hoặc cập nhật giá trị—thay vì dùng một con trỏ duy nhất hoặc lặp lồng nhau.

Có ba dạng thường gặp:

• Con trỏ nhanh–chậm
• Con trỏ đối xứng (đối đầu)
• Cửa sổ trượt

1. Con trỏ nhanh–chậm

Hai con trỏ di chuyển với tốc độ khác nhau: một con "chậm" (mỗi bước tiến 1 đơn vị), một con "nhanh" (mỗi bước tiến 2 đơn vị hoặc nhiều hơn). Dạng này thường xuất hiện trong bài toán liên quan đến danh sách liên kết hoặc chia để trị.

Ví dụ: Kiểm tra chu trình trong danh sách liên kết

Cấu trúc nút danh sách:

struct Node {
    int data;
    Node* next;
    Node(int v) : data(v), next(nullptr) {}
};

Thuật toán:

bool detectLoop(Node* head) {
    if (!head || !head->next) return false;

    Node* pSlow = head;
    Node* pFast = head->next;

    while (pSlow != pFast) {
        if (!pFast || !pFast->next) return false;
        pSlow = pSlow->next;
        pFast = pFast->next->next;
    }

    return true;
}

2. Con trỏ đối xứng (đối đầu)

Hai con trỏ bắt đầu từ hai đầu của cấu trúc dữ liệu (trái và phải), tiến dần vào giữa. Thường áp dụng cho mảng đã sắp xếp hoặc bài toán đối xứng.

Ví dụ: Tìm cặp số trong mảng sắp xếp có tổng bằng giá trị cho trước

std::pair findPairWithSum(const std::vector<int>& arr, int target) {
    int i = 0, j = arr.size() - 1;

    while (i < j) {
        int sum = arr[i] + arr[j];

        if (sum == target) return {i, j};
        else if (sum < target) ++i;
        else --j;
    }

    return {-1, -1}; // không tồn tại cặp
}

3. Cửa sổ trượt

Hai con trỏ tạo thành một "cửa sổ": con đầu (left) giữ vai trò biên trái, con sau (right) mở rộng cửa sổ về phía phải. Khi điều kiện thỏa mãn, ta rút gọn cửa sổ từ bên trái. Thích hợp với các bài toán con liên tục, tối ưu hóa tổng hoặc đếm.

Ví dụ: Tìm độ dài ngắn nhất của dãy con liên tục có tổng ≥ giá trị cho trước

#include <climits>
#include <algorithm>

int shortestSubarraySumAtLeast(std::vector<int>& nums, int minSum) {
    int n = nums.size();
    int left = 0;
    int currSum = 0;
    int minLen = INT_MAX;

    for (int right = 0; right < n; ++right) {
        currSum += nums[right];

        while (currSum >= minSum) {
            minLen = std::min(minLen, right - left + 1);
            currSum -= nums[left];
            ++left;
        }
    }

    return (minLen == INT_MAX) ? 0 : minLen;
}