Phương pháp hai con trỏ

2.1 Định nghĩa phương pháp hai con trỏ.

Phương pháp hai con trỏ — là một kỹ thuật được sử dụng để giải quyết các bài toán khác nhau trên mảng và chuỗi, trong đó sử dụng hai con trỏ (chỉ số) di chuyển qua dữ liệu theo các quy tắc nhất định. Phương pháp này cho phép giải quyết hiệu quả các bài toán liên quan đến tìm kiếm cặp phần tử, tập con thỏa mãn các điều kiện đề ra.

Phương pháp này giả sử sử dụng hai con trỏ, thường được khởi tạo ở hai đầu đối diện của cấu trúc dữ liệu và di chuyển về phía nhau hoặc theo một quy tắc nhất định. Phương pháp hai con trỏ có thể giảm đáng kể độ phức tạp thời gian của thuật toán so với các phương pháp ngây thơ hơn.

Nguyên tắc chính

1. Khởi tạo hai con trỏ: Các con trỏ có thể được đặt ở đầu và cuối của mảng hoặc chuỗi, hoặc ở các chỉ số khác nhau tùy thuộc vào bài toán.
2. Di chuyển các con trỏ: Các con trỏ di chuyển theo một quy tắc nhất định (ví dụ, cả hai con trỏ di chuyển về phía trung tâm, hoặc một con trỏ di chuyển về trước trong khi con trỏ kia đứng yên).
3. Kiểm tra điều kiện: Ở mỗi bước, kiểm tra điều kiện nào quyết định việc di chuyển tiếp hoặc dừng thuật toán.

Độ phức tạp thời gian:

O(n) — trong hầu hết các trường hợp, vì cả hai con trỏ đều đi qua mảng một hoặc nhiều lần, nhưng không quá O(n) lần lặp lại tổng cộng.

Đối với một số bài toán, tùy thuộc vào điều kiện và vị trí ban đầu của các con trỏ, độ phức tạp thời gian có thể là O(n log n) hoặc O(n^2), nhưng điều này rất hiếm.

Ví dụ về các bài toán được giải quyết bằng phương pháp hai con trỏ:

2.2 Tìm hai số trong mảng có tổng bằng một số cho trước.

Bài toán:

Tìm hai số trong mảng đã sắp xếp sao cho tổng của chúng bằng số cho trước target.

Giải quyết:

Khởi tạo một con trỏ ở đầu mảng, con trỏ khác ở cuối. Kiểm tra tổng của các phần tử dưới các con trỏ:

• Nếu tổng bằng target, trả về các chỉ số.
• Nếu tổng nhỏ hơn target, di chuyển con trỏ trái sang phải.
• Nếu tổng lớn hơn target, di chuyển con trỏ phải sang trái.

Độ phức tạp thời gian: O(n).

Ví dụ mã Python:

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return left, right
        elif s < target:
            left += 1
        else:
            right -= 1
    return None
        

2.3 Kiểm tra palindrome

Bài toán:

Kiểm tra xem một chuỗi có phải là palindrome không.

Giải quyết:

Khởi tạo con trỏ ở đầu và cuối của chuỗi. So sánh các ký tự dưới các con trỏ:

• Nếu các ký tự bằng nhau, di chuyển cả hai con trỏ về phía nhau.
• Nếu các ký tự không bằng nhau, chuỗi không phải là palindrome.

Độ phức tạp thời gian: O(n).

Ví dụ mã Python:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
        

2.4 Xóa các bản sao từ mảng đã sắp xếp

Bài toán:

Xóa các bản sao từ mảng đã sắp xếp.

Giải quyết:

Sử dụng hai con trỏ, một cho vị trí hiện tại trong mảng kết quả, một để duyệt qua tất cả các phần tử:

• Nếu phần tử hiện tại không bằng phần tử trước đó, ghi nó vào mảng kết quả.

Độ phức tạp thời gian: O(n).

Ví dụ mã Python:

def remove_duplicates(arr):
    if not arr:
        return 0
    write_index = 1
    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:
            arr[write_index] = arr[i]
            write_index += 1
    return write_index