Two Pointers (hai con trỏ) là kỹ thuật dùng hai chỉ số và di chuyển cùng chiều (hoặc ngược chiều) để xử lý mảng/xâu trong thay vì .
Dạng 1: Sliding Window (cùng chiều)
và cùng di chuyển sang phải. Duy trì cửa sổ thỏa điều kiện nào đó.
Ứng dụng: Tìm đoạn con ngắn nhất/dài nhất thỏa điều kiện.
// Đoạn con dài nhất có tổng <= K
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];
while (sum > K) sum -= a[l++];
ans = max(ans, r - l + 1);
}
return ans;
}
// Đoạn con ngắn nhất có tổng >= K
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)
bắt đầu từ trái, từ phải, di chuyển vào giữa.
Ứng dụng: Tìm cặp với thỏa điều kiện trên mảng đã sắp xếp.
// Đếm cặp (i,j) với a[i]+a[j] = target (mảng đã sort)
int count_pairs(vector<int>& a, int target) {
int l = 0, r = a.size() - 1, cnt = 0;
while (l < r) {
int s = a[l] + a[r];
if (s == target) {
// Đếm số lượng a[l] và a[r] trùng nhau (nếu cần)
cnt++;
l++; r--;
} else if (s < target) l++;
else r--;
}
return cnt;
}
// Kiểm tra có cặp nào tổng = target không
bool has_pair(vector<int>& a, int target) {
sort(a.begin(), a.end());
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++;
else r--;
}
return false;
}
Dạng 3: Two Pointers trên hai mảng
// Đế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) {
int na = a.size(), nb = b.size();
long long cnt = 0;
int j = nb - 1;
for (int i = 0; i < na; i++) {
while (j >= 0 && a[i] + b[j] > K) j--;
cnt += j + 1;
}
return cnt;
}
Ứng dụng thực tế
Longest Substring Without Repeating Characters:
int longest_unique(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++]]--;
ans = max(ans, r - l + 1);
}
return ans;
}
Số đoạn con có tích âm:
// Đếm đoạn con có tích âm trong mảng số thực dương/âm
// → đếm đoạn con có số lượng phần tử âm lẻ
Khi nào dùng Two Pointers?
- Mảng đã sắp xếp + tìm cặp/bộ thỏa điều kiện tổng.
- Tìm đoạn con tối ưu với điều kiện monotone (thêm phần tử làm xấu hơn hoặc tốt hơn đơn điệu).
- Thay thế brute force khi cửa sổ có thể shrink/expand đơn điệu.
Điều kiện cần: Khi mở rộng cửa sổ sang phải, trạng thái chỉ thay đổi một chiều (tổng tăng, số lượng phân biệt tăng,...) — cho phép chỉ di chuyển sang phải, không quay lại.
Bình luận