Kỹ thuật hai con trỏ (Two-Pointer) là một trong những phương pháp tối ưu nhất để xử lý các bài toán trên mảng hoặc chuỗi. Thay vì sử dụng các vòng lặp lồng nhau gây tốn kém về thời gian (O(n²)), hai con trỏ giúp đưa độ phức tạp về O(n). Dưới đây là cách áp dụng kỹ thuật này vào các bài toán thực tế.

1. Loại bỏ phần tử (LeetCode 27)

Bài toán yêu cầu loại bỏ các phần tử có giá trị cụ thể ra khỏi mảng ngay tại chỗ (in-place). Kỹ thuật con trỏ nhanh-chậm là lựa chọn tối ưu ở đây.

class Solution {
    public int removeElement(int[] arr, int target) {
        int slowIdx = 0;
        // Con trỏ fastIdx dùng để duyệt qua toàn bộ mảng
        for (int fastIdx = 0; fastIdx < arr.length; fastIdx++) {
            // Nếu phần tử hiện tại khác giá trị cần loại bỏ
            if (arr[fastIdx] != target) {
                arr[slowIdx] = arr[fastIdx];
                slowIdx++;
            }
        }
        return slowIdx; // Trả về độ dài mới của mảng
    }
}

2. Bình phương của mảng đã sắp xếp (LeetCode 977)

Với một mảng đã sắp xếp (có thể chứa số âm), bình phương của các số lớn nhất sẽ nằm ở hai đầu mảng. Do đó, ta sử dụng con trỏ hướng vào nhau từ hai đầu.

class Solution {
    public int[] sortedSquares(int[] numbers) {
        int n = numbers.length;
        int[] result = new int[n];
        int left = 0, right = n - 1;
        int currentPos = n - 1;

        while (left <= right) {
            int leftVal = numbers[left] * numbers[left];
            int rightVal = numbers[right] * numbers[right];
            
            if (leftVal > rightVal) {
                result[currentPos--] = leftVal;
                left++;
            } else {
                result[currentPos--] = rightVal;
                right--;
            }
        }
        return result;
    }
}

3. Di chuyển các số 0 (LeetCode 283)

Tương tự như bài toán loại bỏ phần tử, ta dùng con trỏ chậm để đánh dấu vị trí ghi tiếp theo và con trỏ nhanh để tìm các số khác 0.

class Solution {
    public void moveZeroes(int[] nums) {
        int writePtr = 0;
        // Đưa các số khác 0 lên phía trước
        for (int readPtr = 0; readPtr < nums.length; readPtr++) {
            if (nums[readPtr] != 0) {
                nums[writePtr++] = nums[readPtr];
            }
        }
        // Điền các vị trí còn lại bằng số 0
        while (writePtr < nums.length) {
            nums[writePtr++] = 0;
        }
    }
}

4. Chứa nhiều nước nhất (LeetCode 11)

Để tìm diện tích lớn nhất, ta dùng hai con trỏ ở hai đầu mảng. Diện tích bị giới hạn bởi cột thấp hơn, vì vậy ta luôn dịch chuyển con trỏ ở cột thấp hơn để tìm kiếm cơ hội có cột cao hơn.

class Solution {
    public int maxArea(int[] heights) {
        int low = 0, high = heights.length - 1;
        int maxCapacity = 0;
        
        while (low < high) {
            int width = high - low;
            int h = Math.min(heights[low], heights[high]);
            maxCapacity = Math.max(maxCapacity, width * h);
            
            // Dịch chuyển cột thấp hơn
            if (heights[low] < heights[high]) {
                low++;
            } else {
                high--;
            }
        }
        return maxCapacity;
    }
}

5. Tổng ba số (LeetCode 15)

Để tránh trùng lặp và tối ưu hóa, mảng cần được sắp xếp trước. Sau đó, ta cố định một số và dùng hai con trỏ để tìm hai số còn lại sao cho tổng bằng 0.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue; // Bỏ qua phần tử trùng
            
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return result;
    }
}

6. Hứng nước mưa (LeetCode 42)

Đây là bài toán nâng cao sử dụng hai con trỏ để theo dõi độ cao lớn nhất từ bên trái và bên phải, từ đó tính toán lượng nước có thể giữ được tại mỗi vị trí.

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length < 3) return 0;
        
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int totalWater = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    totalWater += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    totalWater += rightMax - height[right];
                }
                right--;
            }
        }
        return totalWater;
    }
}