Tổng quan về kỹ thuật hai con trỏ
Kỹ thuật hai con trỏ (Two Pointers) là một phương pháp tối ưu hóa thuật toán hiệu quả, giúp giảm độ phức tạp thời gian trong nhiều bài toán. Thay vì sử dụng vòng lặp lồng nhau với độ phức tạp $O(n^2)$, ta sử dụng hai biến chỉ số (con trỏ) để duyệt qua cấu trúc dữ liệu, thường là mảng hoặc danh sách liên kết.
Cách tiếp cận này đặc biệt hữu ích khi làm việc với các dãy con hoặc các vấn đề có tính đơn điệu (monotonicity). Bài viết này sẽ đi sâu vào các biến thể phổ biến của kỹ thuật này, bao gồm duyệt tuyến tính và gộp mảng (merging).
Duyệt tuyến tính với hai con trỏ
1. Đếm mảng con có tích nhỏ hơn K
Đề bài: Cho một mảng số nguyên dương và một số nguyên $k$. Hãy đếm số lượng mảng con liên tiếp mà tích của tất cả các phần tử trong mảng con đó nhỏ hơn $k$.
Cách giải quyết tối ưu nhất là sử dụng kỹ thuật cửa sổ trượt (sliding window) - một dạng của hai con trỏ. Ta duy trì một cửa sổ $[left, right]$ sao cho tích các phần tử bên trong luôn nhỏ hơn $k$.
Ý tưởng chính:
- Dịch con trỏ
rightsang phải để mở rộng cửa sổ và cập nhật tích. - Nếu tích $\ge k$, dịch con trỏ
leftsang phải để thu hẹp cửa sổ và chia tích cho phần tử bị loại bỏ. - Tại mỗi bước, nếu cửa sổ hiện tại hợp lệ, tất cả các mảng con kết thúc tại vị trí
rightvà bắt đầu từ bất kỳ vị trí nào trong $[left, right]$ đều thỏa mãn. Số lượng mảng con tăng thêm là $right - left + 1$.
Mã nguồn C++:
#include <vector>
using namespace std;
class Solution {
public:
int countSubarrays(vector<int>& nums, int k) {
if (k <= 1) return 0;
long long product = 1;
int left = 0;
int result = 0;
for (int right = 0; right < nums.size(); ++right) {
product *= nums[right];
// Thu hẹp cửa sổ từ bên trái nếu tích vượt quá k
while (product >= k) {
product /= nums[left];
left++;
}
// Các mảng con kết thúc tại 'right' và bắt đầu từ left...right đều hợp lệ
result += right - left + 1;
}
return result;
}
};
2. Dãy con dài nhất không chứa phần tử trùng lặp
Đề bài: Tìm độ dài của chuỗi con liên tiếp dài nhất mà không có bất kỳ ký tự nào lặp lại.
Ta sử dụng hai con trỏ để duy trì một đoạn $[start, i]$ không chứa ký tự trùng lặp. Sử dụng một bảng băm (hash map) hoặc mảng đánh dấu để lưu vị trí xuất hiện cuối cùng của từng ký tự.
Mã nguồn C++:
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> lastIndex;
int maxLength = 0;
int start = -1;
for (int i = 0; i < s.length(); ++i) {
char currentChar = s[i];
// Nếu ký tự đã xuất hiện trong cửa sổ hiện tại
if (lastIndex.count(currentChar) && lastIndex[currentChar] > start) {
start = lastIndex[currentChar];
}
lastIndex[currentChar] = i;
maxLength = max(maxLength, i - start);
}
return maxLength;
}
3. Kiểm tra chuỗi con (Subsequence)
Đề bài: Kiểm tra xem chuỗi t có phải là chuỗi con của chuỗi s hay không. Chuỗi con không cần liên tiếp nhưng phải giữ đúng thứ tự xuất hiện.
Sử dụng hai con trỏ, một cho chuỗi gốc s và một cho chuỗi đích t. Duyệt qua s, nếu gặp ký tự trùng khớp với con trỏ hiện tại của t, ta dịch con trỏ của t lên. Nếu con trỏ của t đi đến hết chuỗi, nghĩa là t là chuỗi con của s.
Mã nguồn C++:
#include <iostream>
#include <string>
using namespace std;
bool isSubsequence(string t, string s) {
int iterT = 0, iterS = 0;
int lenT = t.length(), lenS = s.length();
while (iterS < lenS && iterT < lenT) {
if (s[iterS] == t[iterT]) {
iterT++;
}
iterS++;
}
return iterT == lenT;
}
Kỹ thuật gộp mảng (Merge)
Gộp hai dãy có thứ tự
Kỹ thuật hai con trỏ cho phép gộp hai mảng đã được sắp xếp thành một mảng mới có thứ tự trong thời gian tuyến tính $O(n)$. Đây là nền tảng của thuật toán Sắp xếp trộn (Merge Sort).
Mã nguồn minh họa:
void mergeArrays(vector<int>& result, vector<int>& a, vector<int>& b) {
int i = 0, j = 0, k = 0;
while (i < a.size() && j < b.size()) {
if (a[i] <= b[j]) {
result[k++] = a[i++];
} else {
result[k++] = b[j++];
}
}
while (i < a.size()) result[k++] = a[i++];
while (j < b.size()) result[k++] = b[j++];
}
Ví dụ: Bài toán Vòng quay Thụy Sĩ (Swiss Round)
Trong bài toán này (ví dụ Luogu P1309), sau mỗi vòng đấu, người thắng và người thua được chia thành hai nhóm. Do danh sách ban đầu có thứ tự, và sau khi thi đấu xong, người thắng và người thua trong các cặp đấu thường cũng mang tính thứ tự tương đối. Thay vì sắp xếp lại toàn bộ danh sách ($O(N \log N)$) ở mỗi vòng, ta có thể tách người thắng và người thua vào hai danh sách riêng biệt, sau đó dùng kỹ thuật hai con trỏ để gộp chúng lại trong $O(N)$. Điều này giúp giảm đáng kể thời gian chạy.
Sắp xếp trộn (Merge Sort) và Cặp nghịch thế
Sắp xếp trộn dựa trên tư duy "Chia để trị" (Divide and Conquer). Mảng được chia liên tục cho đến khi còn từng phần tử đơn lẻ, sau đó quá trình gộp (merge) diễn ra để sắp xếp các phần tử.
Triển khai Merge Sort
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (int p = 0; p < k; p++) {
arr[left + p] = temp[p];
}
}
void mergeSort(vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
Đếm cặp nghịch thế (Inversion Pairs)
Một cặp nghịch thế là cặp chỉ số $(i, j)$ mà $i < j$ nhưng $A[i] > A[j]$. Sắp xếp trộn có thể được sửa đổi nhẹ để đếm số lượng cặp này.
Vào quá trình merge, khi ta lấy phần tử từ mảng phải (arr[j]) vào trước mảng trái (arr[i]), điều này có nghĩa là arr[j] nhỏ hơn tất cả các phần tử còn lại trong mảng trái (từ arr[i] đến arr[mid]). Do đó, số lượng cặp nghịch thế tăng thêm là mid - i + 1.
Mã nguồn đếm cặp nghịch thế:
#include <iostream>
#include <vector>
using namespace std;
long long inversionCount = 0;
void mergeAndCount(vector<int>& arr, int left, int mid, int right) {
vector<int> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
// Phần tử arr[j] nhỏ hơn các phần tử từ arr[i] đến arr[mid]
inversionCount += (mid - i + 1);
temp[k++] = arr[j++];
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (int p = 0; p < k; p++) {
arr[left + p] = temp[p];
}
}
void mergeSortCount(vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSortCount(arr, left, mid);
mergeSortCount(arr, mid + 1, right);
mergeAndCount(arr, left, mid, right);
}
}