Khóa học Python từ Cơ bản đến Nâng cao

Bài 7.2 - Two pointers - thuật toán Python cơ bản

Chào mừng bạn đến với bài viết chuyên sâu về một trong những kỹ thuật thuật toán cơ bản nhưng cực kỳ mạnh mẽ trong lập trình: Two Pointers (Kỹ thuật Hai Con Trỏ). Nếu bạn đã từng gặp các bài toán cần duyệt hoặc xử lý các phần tử trong một mảng (hoặc danh sách) hoặc chuỗi một cách hiệu quả, nhiều khả năng Two Pointers chính là giải pháp mà bạn đang tìm kiếm. Đây là một công cụ thiết yếu giúp bạn tối ưu hóa đáng kể thời gian và không gian cho nhiều bài toán, biến các giải pháp O(n^2) thành O(n) chỉ bằng việc sử dụng hai chỉ mục (hay còn gọi là "con trỏ") để duyệt cấu trúc dữ liệu.

Two Pointers là gì?

Nói một cách đơn giản, kỹ thuật Two Pointers liên quan đến việc sử dụng hai biến (thường là các chỉ mục hoặc vị trí) để cùng nhau duyệt qua một cấu trúc dữ liệu, phổ biến nhất là mảng hoặc danh sách (list) trong Python, hoặc một chuỗi (string). Các con trỏ này có thể bắt đầu ở những vị trí khác nhau và di chuyển theo các hướng khác nhau, tùy thuộc vào bản chất của bài toán cần giải quyết.

Mục tiêu chính của việc sử dụng hai con trỏ là:

1. Giảm độ phức tạp thời gian: Thay vì sử dụng các vòng lặp lồng nhau (thường dẫn đến O(n^2)), kỹ thuật Two Pointers cho phép chúng ta giải quyết nhiều bài toán chỉ với một lần duyệt duy nhất O(n).
2. Giảm độ phức tạp không gian: Thường các giải pháp Two Pointers có thể thực hiện "in-place" (ngay trên cấu trúc dữ liệu gốc) mà không cần thêm không gian bộ nhớ phụ đáng kể, đạt độ phức tạp không gian O(1).

Khi nào nên sử dụng Two Pointers?

Kỹ thuật này đặc biệt hiệu quả khi bạn cần làm việc với các cấu trúc dữ liệu có thứ tự (như mảng đã sắp xếp, chuỗi) hoặc khi bài toán liên quan đến việc tìm kiếm cặp phần tử, các phần tử trùng lặp, hoặc các đoạn con (subarray/substring) có tính chất nhất định.

Có hai mô hình di chuyển con trỏ phổ biến:

1. Hai con trỏ di chuyển từ hai phía vào giữa: Thường áp dụng cho mảng đã sắp xếp. Một con trỏ bắt đầu ở đầu mảng, con trỏ kia ở cuối mảng. Chúng di chuyển dần vào trung tâm dựa trên điều kiện của bài toán.
2. Hai con trỏ di chuyển cùng chiều: Một con trỏ (thường gọi là slow pointer) di chuyển chậm hơn con trỏ kia (thường gọi là fast pointer). Con trỏ nhanh duyệt qua cấu trúc dữ liệu, và con trỏ chậm di chuyển hoặc thực hiện hành động nào đó dựa trên vị trí hoặc giá trị của con trỏ nhanh. Kỹ thuật này đôi khi còn được gọi là Sliding Window khi hai con trỏ định nghĩa một "cửa sổ" kích thước động hoặc cố định.

Bây giờ, chúng ta hãy đi sâu vào một số ví dụ minh họa cụ thể để thấy rõ sự linh hoạt và hiệu quả của kỹ thuật Two Pointers trong Python.

Ví dụ 1: Tìm cặp phần tử có tổng bằng giá trị mục tiêu trong mảng đã sắp xếp (Two pointers di chuyển từ hai phía)

Đây là một bài toán kinh điển cho kỹ thuật Two Pointers.

Bài toán: Cho một mảng các số nguyên đã được sắp xếp theo thứ tự tăng dần và một số nguyên mục tiêu target. Tìm xem có tồn tại một cặp số trong mảng có tổng bằng target hay không.

Cách tiếp cận thông thường (Brute-force): Sử dụng hai vòng lặp lồng nhau để kiểm tra tất cả các cặp có thể. Độ phức tạp thời gian là O(n^2).

Cách tiếp cận Two Pointers: Vì mảng đã được sắp xếp, chúng ta có thể tận dụng thông tin này. Sử dụng hai con trỏ:

• left: Bắt đầu ở chỉ mục 0 (phần tử nhỏ nhất).
• right: Bắt đầu ở chỉ mục n-1 (phần tử lớn nhất), với n là độ dài mảng.

Chúng ta kiểm tra tổng của arr[left] và arr[right]:

• Nếu tổng bằng target, chúng ta đã tìm thấy cặp và kết thúc.
• Nếu tổng nhỏ hơn target, điều đó có nghĩa là chúng ta cần một tổng lớn hơn. Để tăng tổng, chúng ta phải tăng giá trị của một trong hai phần tử. Vì arr[right] là phần tử lớn nhất có thể có ở phía bên phải, việc giảm right sẽ làm giảm hoặc giữ nguyên tổng. Do đó, chúng ta cần tăng arr[left] bằng cách di chuyển left sang phải (left += 1).
• Nếu tổng lớn hơn target, chúng ta cần một tổng nhỏ hơn. Để giảm tổng, chúng ta phải giảm giá trị của một trong hai phần tử. Vì arr[left] là phần tử nhỏ nhất có thể có ở phía bên trái, việc tăng left sẽ làm tăng hoặc giữ nguyên tổng. Do đó, chúng ta cần giảm arr[right] bằng cách di chuyển right sang trái (right -= 1).

Chúng ta tiếp tục quá trình này cho đến khi left >= right. Nếu vòng lặp kết thúc mà không tìm thấy cặp nào, thì không có cặp nào thỏa mãn.

Code minh họa bằng Python:

def find_pair_with_sum(arr, target):
    """
    Tìm cặp phần tử có tổng bằng target trong mảng đã sắp xếp.

    Args:
        arr: Danh sách các số nguyên đã sắp xếp.
        target: Tổng mục tiêu.

    Returns:
        True nếu tìm thấy cặp, False nếu không tìm thấy.
        (Có thể trả về cặp chỉ mục hoặc giá trị nếu cần)
    """
    left = 0
    right = len(arr) - 1

    while left < right:
        current_sum = arr[left] + arr[right]

        if current_sum == target:
            # Tìm thấy cặp
            print(f"Tìm thấy cặp ({arr[left]}, {arr[right]}) với tổng {target}")
            return True # Hoặc return (left, right) nếu muốn trả về chỉ mục
        elif current_sum < target:
            # Tổng quá nhỏ, cần tăng arr[left]
            left += 1
        else: # current_sum > target
            # Tổng quá lớn, cần giảm arr[right]
            right -= 1

    # Duyệt hết mà không tìm thấy
    print(f"Không tìm thấy cặp nào có tổng {target}")
    return False

# Ví dụ sử dụng
sorted_numbers = [1, 3, 4, 5, 7, 10, 11]
target_sum_1 = 9
target_sum_2 = 20
target_sum_3 = 2

find_pair_with_sum(sorted_numbers, target_sum_1)
find_pair_with_sum(sorted_numbers, target_sum_2)
find_pair_with_sum(sorted_numbers, target_sum_3)

Giải thích code:

1. left và right được khởi tạo ở hai đầu của danh sách arr.
2. Vòng lặp while left < right: tiếp tục chừng nào hai con trỏ chưa gặp hoặc vượt qua nhau. Điều kiện left < right đảm bảo chúng ta đang xét hai phần tử khác nhau và con trỏ trái luôn ở bên trái con trỏ phải.
3. current_sum = arr[left] + arr[right] tính tổng của hai phần tử hiện tại được trỏ bởi left và right.
4. Nếu current_sum == target: Chúng ta đã tìm thấy cặp số có tổng bằng mục tiêu. In thông báo và trả về True.
5. Nếu current_sum < target: Tổng hiện tại quá nhỏ. Để tăng tổng, chúng ta cần một số lớn hơn ở phía trái. Do mảng đã sắp xếp, di chuyển left sang phải (left += 1) sẽ đưa chúng ta đến một phần tử có giá trị lớn hơn hoặc bằng arr[left] hiện tại, giúp tăng tổng.
6. Nếu không (tức là current_sum > target): Tổng hiện tại quá lớn. Để giảm tổng, chúng ta cần một số nhỏ hơn ở phía phải. Do mảng đã sắp xếp, di chuyển right sang trái (right -= 1) sẽ đưa chúng ta đến một phần tử có giá trị nhỏ hơn hoặc bằng arr[right] hiện tại, giúp giảm tổng.
7. Nếu vòng lặp kết thúc mà điều kiện current_sum == target chưa bao giờ được đáp ứng, điều đó có nghĩa là không có cặp nào trong mảng có tổng bằng target. Trả về False.

Độ phức tạp thời gian của giải pháp này là O(n) vì mỗi con trỏ chỉ di chuyển theo một hướng và tối đa n bước. Độ phức tạp không gian là O(1) vì chúng ta chỉ sử dụng một vài biến phụ.

Ví dụ 2: Kiểm tra chuỗi Palindrome (Two pointers di chuyển từ hai phía)

Bài toán: Kiểm tra xem một chuỗi có phải là palindrome hay không. Một chuỗi được gọi là palindrome nếu đọc xuôi và đọc ngược đều giống nhau, không phân biệt hoa thường và bỏ qua các ký tự không phải là chữ cái hoặc số.

Cách tiếp cận Two Pointers: Sử dụng hai con trỏ:

• left: Bắt đầu ở chỉ mục 0 (ký tự đầu tiên).
• right: Bắt đầu ở chỉ mục n-1 (ký tự cuối cùng), với n là độ dài chuỗi.

Chúng ta di chuyển left sang phải và right sang trái, đồng thời bỏ qua các ký tự không phải là chữ cái hoặc số. Sau khi tìm được hai ký tự hợp lệ ở vị trí left và right, chúng ta so sánh chúng (chuyển về cùng một kiểu chữ, ví dụ chữ thường).

• Nếu chúng khác nhau, chuỗi không phải là palindrome.
• Nếu chúng giống nhau, tiếp tục di chuyển left và right.

Quá trình dừng khi left >= right. Nếu vòng lặp kết thúc mà không tìm thấy cặp ký tự khác nhau nào, thì chuỗi là palindrome.

Code minh họa bằng Python:

import re # Import module regex để lọc ký tự

def is_palindrome(s):
    """
    Kiểm tra xem chuỗi có phải là palindrome không (bỏ qua ký tự không hợp lệ và phân biệt hoa thường).

    Args:
        s: Chuỗi đầu vào.

    Returns:
        True nếu là palindrome, False nếu không.
    """
    # Bước 1: Lọc và chuẩn hóa chuỗi (chỉ giữ lại chữ cái và số, chuyển về chữ thường)
    # Dùng regex để loại bỏ tất cả ký tự không phải chữ cái (a-z, A-Z) hoặc số (0-9)
    cleaned_s = re.sub(r'[^a-zA-Z0-9]', '', s).lower()

    left = 0
    right = len(cleaned_s) - 1

    # Bước 2: Dùng Two Pointers để so sánh
    while left < right:
        # So sánh ký tự ở hai vị trí
        if cleaned_s[left] != cleaned_s[right]:
            # Nếu khác nhau, không phải palindrome
            return False

        # Di chuyển con trỏ vào giữa
        left += 1
        right -= 1

    # Nếu vòng lặp hoàn thành, nghĩa là tất cả các cặp đều khớp
    return True

# Ví dụ sử dụng
string1 = "A man, a plan, a canal: Panama"
string2 = "race a car"
string3 = "Level"
string4 = "hello"

print(f"'{string1}' là palindrome? {is_palindrome(string1)}")
print(f"'{string2}' là palindrome? {is_palindrome(string2)}")
print(f"'{string3}' là palindrome? {is_palindrome(string3)}")
print(f"'{string4}' là palindrome? {is_palindrome(string4)}")

Giải thích code:

1. Hàm is_palindrome(s) nhận một chuỗi s.
2. re.sub(r'[^a-zA-Z0-9]', '', s) sử dụng biểu thức chính quy (regex) để thay thế tất cả các ký tự không nằm trong tập a-zA-Z0-9 (chữ cái và số) bằng chuỗi rỗng (''). Kết quả là một chuỗi chỉ chứa chữ cái và số.
3. .lower() chuyển chuỗi đã lọc sang chữ thường để bỏ qua sự khác biệt về hoa thường. Kết quả được lưu vào cleaned_s.
4. left và right được khởi tạo ở hai đầu của cleaned_s.
5. Vòng lặp while left < right: tiếp tục so sánh chừng nào hai con trỏ chưa gặp nhau.
6. Trong mỗi lần lặp, if cleaned_s[left] != cleaned_s[right]: so sánh ký tự ở vị trí left và right. Nếu chúng khác nhau, chuỗi gốc không thể là palindrome (theo định nghĩa của bài toán này), nên trả về False.
7. Nếu hai ký tự giống nhau, chúng ta di chuyển left sang phải (left += 1) và right sang trái (right -= 1) để kiểm tra cặp ký tự tiếp theo.
8. Nếu vòng lặp kết thúc mà chưa trả về False, điều đó có nghĩa là tất cả các cặp ký tự tương ứng đều giống nhau, và chuỗi là palindrome. Trả về True.

Độ phức tạp thời gian: Việc lọc và chuẩn hóa chuỗi mất O(n) (với n là độ dài chuỗi gốc). Vòng lặp Two Pointers cũng mất O(n) vì mỗi con trỏ di chuyển tối đa n/2 bước. Tổng cộng là O(n). Độ phức tạp không gian là O(n) cho việc tạo chuỗi cleaned_s. Tuy nhiên, nếu bài toán cho phép xử lý trực tiếp trên chuỗi gốc và chỉ so sánh các ký tự hợp lệ, chúng ta có thể tối ưu không gian xuống O(1) bằng cách thêm các vòng lặp while nhỏ để bỏ qua ký tự không hợp lệ ngay trong vòng lặp chính.

Ví dụ 3: Loại bỏ phần tử trùng lặp khỏi mảng đã sắp xếp (Two pointers di chuyển cùng chiều)

Bài toán: Cho một mảng các số nguyên đã được sắp xếp. Hãy loại bỏ các phần tử trùng lặp ngay tại chỗ (in-place) sao cho mỗi phần tử chỉ xuất hiện một lần duy nhất. Trả về độ dài mới của mảng. Các phần tử sau độ dài mới không quan trọng.

Cách tiếp cận Two Pointers: Sử dụng hai con trỏ di chuyển cùng chiều:

• slow (hoặc write_index): Chỉ vị trí tiếp theo mà một phần tử duy nhất nên được ghi vào. Bắt đầu từ chỉ mục 0.
• fast (hoặc read_index): Duyệt qua toàn bộ mảng để tìm các phần tử mới. Bắt đầu từ chỉ mục 1.

Chúng ta duyệt mảng bằng con trỏ fast. Nếu arr[fast] là một phần tử mới (tức là khác với arr[slow]), chúng ta tăng slow lên 1 và sao chép giá trị arr[fast] vào vị trí arr[slow]. Nếu arr[fast] là phần tử trùng lặp (giống với arr[slow]), chúng ta bỏ qua nó và chỉ tăng fast.

Code minh họa bằng Python:

def remove_duplicates(arr):
    """
    Loại bỏ các phần tử trùng lặp khỏi mảng đã sắp xếp ngay tại chỗ.

    Args:
        arr: Danh sách các số nguyên đã sắp xếp.

    Returns:
        Độ dài mới của mảng sau khi loại bỏ trùng lặp.
        (Mảng gốc arr đã được sửa đổi)
    """
    if not arr: # Xử lý trường hợp danh sách rỗng
        return 0

    # slow pointer chỉ vị trí tiếp theo để ghi phần tử duy nhất
    slow = 0

    # fast pointer duyệt qua mảng
    for fast in range(1, len(arr)):
        # Nếu phần tử được trỏ bởi fast khác với phần tử được trỏ bởi slow
        # (tức là tìm thấy một phần tử mới duy nhất)
        if arr[fast] != arr[slow]:
            # Tăng slow lên 1 để chuẩn bị cho vị trí ghi tiếp theo
            slow += 1
            # Sao chép phần tử mới từ vị trí fast sang vị trí slow
            arr[slow] = arr[fast]

    # Độ dài mới của mảng là slow + 1 (vì slow bắt đầu từ 0)
    new_length = slow + 1
    # (Các phần tử từ chỉ mục new_length trở đi không quan trọng)
    # print(f"Mảng sau khi xử lý: {arr[:new_length]}") # Có thể in ra để kiểm tra

    return new_length

# Ví dụ sử dụng
sorted_array_with_duplicates = [1, 1, 2, 2, 3, 4, 4, 4, 5]
new_len = remove_duplicates(sorted_array_with_duplicates)
print(f"Độ dài mới của mảng: {new_len}")
print(f"Mảng sau khi loại bỏ trùng lặp (chỉ lấy các phần tử đến độ dài mới): {sorted_array_with_duplicates[:new_len]}")

sorted_array_no_duplicates = [1, 2, 3, 4, 5]
new_len_2 = remove_duplicates(sorted_array_no_duplicates)
print(f"Độ dài mới của mảng: {new_len_2}")
print(f"Mảng sau khi loại bỏ trùng lặp: {sorted_array_no_duplicates[:new_len_2]}")

Giải thích code:

1. Hàm remove_duplicates(arr) nhận một danh sách đã sắp xếp arr.
2. Kiểm tra trường hợp danh sách rỗng.
3. slow được khởi tạo tại chỉ mục 0. Đây là vị trí mà chúng ta sẽ ghi phần tử duy nhất đầu tiên.
4. Vòng lặp for fast in range(1, len(arr)): sử dụng fast để duyệt qua mảng bắt đầu từ chỉ mục 1.
5. if arr[fast] != arr[slow]: là điều kiện chính. Nếu phần tử hiện tại được trỏ bởi fast khác với phần tử được trỏ bởi slow, điều đó có nghĩa là arr[fast] là một phần tử mới mà chúng ta chưa thấy ở vị trí slow trở về trước.
6. Khi tìm thấy phần tử mới, chúng ta tăng slow lên 1 (slow += 1) để chuyển đến vị trí trống tiếp theo trong phần "duy nhất" của mảng. Sau đó, sao chép giá trị arr[fast] vào vị trí arr[slow].
7. Nếu arr[fast] bằng arr[slow], điều đó có nghĩa là arr[fast] là một phần tử trùng lặp. Chúng ta không làm gì với slow và chỉ đơn giản là vòng lặp for tự động tăng fast lên để kiểm tra phần tử tiếp theo.
8. Sau khi vòng lặp kết thúc, slow sẽ chỉ vào chỉ mục cuối cùng của phần tử duy nhất cuối cùng trong mảng đã sửa đổi. Do đó, độ dài mới của mảng là slow + 1.
9. Hàm trả về slow + 1. Danh sách arr gốc đã được sửa đổi trực tiếp.

Độ phức tạp thời gian của giải pháp này là O(n) vì con trỏ fast duyệt qua mảng một lần duy nhất, và slow cũng di chuyển tối đa n bước. Độ phức tạp không gian là O(1) vì chúng ta thực hiện sửa đổi ngay tại chỗ mà không cần thêm cấu trúc dữ liệu phụ có kích thước phụ thuộc vào n.

Ví dụ 4: Container With Most Water (Two pointers di chuyển từ hai phía)

Bài toán: Cho một danh sách các số nguyên height biểu thị chiều cao của các đường thẳng đứng. Hai đầu mút của đường thẳng tại chỉ mục i là (i, 0) và (i, height[i]). Tìm hai đường thẳng tạo thành một container chứa được nhiều nước nhất.

Cách tiếp cận Two Pointers: Nếu dùng cách vét cạn (brute-force), kiểm tra mọi cặp đường thẳng, độ phức tạp là O(n^2). Kỹ thuật Two Pointers có thể tối ưu bài toán này. Sử dụng hai con trỏ:

• left: Bắt đầu ở chỉ mục 0.
• right: Bắt đầu ở chỉ mục n-1.

Diện tích của container tạo bởi height[left] và height[right] là min(height[left], height[right]) * (right - left). Để tối đa hóa diện tích, chúng ta cần tăng cả chiều cao (min(h_l, h_r)) lẫn chiều rộng (right - left). Bắt đầu với chiều rộng lớn nhất (right - left). Ở mỗi bước, chúng ta tính diện tích hiện tại và cập nhật diện tích tối đa. Sau đó, chúng ta cần di chuyển một trong hai con trỏ. Nên di chuyển con trỏ nào?

• Nếu di chuyển con trỏ có chiều cao lớn hơn, chiều cao tối thiểu của container mới chắc chắn sẽ không tăng lên (vì nó bị giới hạn bởi đường còn lại) và chiều rộng giảm đi. Điều này có thể làm giảm diện tích.
• Nếu di chuyển con trỏ có chiều cao nhỏ hơn, chiều cao tối thiểu của container mới có khả năng tăng lên (nếu đường mới cao hơn đường cũ), bù đắp cho việc chiều rộng giảm đi, và có thể dẫn đến diện tích lớn hơn.

Do đó, chiến lược là luôn di chuyển con trỏ trỏ đến đường thẳng có chiều cao thấp hơn.

Code minh họa bằng Python:

def max_area(height):
    """
    Tìm container chứa nhiều nước nhất.

    Args:
        height: Danh sách các số nguyên biểu thị chiều cao của các đường thẳng.

    Returns:
        Lượng nước tối đa có thể chứa.
    """
    left = 0
    right = len(height) - 1
    max_water = 0

    while left < right:
        # Chiều cao của container được giới hạn bởi đường ngắn hơn
        h = min(height[left], height[right])
        # Chiều rộng của container là khoảng cách giữa hai đường
        w = right - left
        # Tính diện tích hiện tại
        current_water = h * w

        # Cập nhật lượng nước tối đa nếu diện tích hiện tại lớn hơn
        max_water = max(max_water, current_water)

        # Di chuyển con trỏ của đường ngắn hơn
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

# Ví dụ sử dụng
heights1 = [1, 8, 6, 2, 5, 4, 8, 3, 7] # Output: 49
heights2 = [1, 1] # Output: 1
heights3 = [4, 3, 2, 1, 4] # Output: 16
heights4 = [1, 2, 1] # Output: 2

print(f"Container với heights={heights1} chứa tối đa: {max_area(heights1)}")
print(f"Container với heights={heights2} chứa tối đa: {max_area(heights2)}")
print(f"Container với heights={heights3} chứa tối đa: {max_area(heights3)}")
print(f"Container với heights={heights4} chứa tối đa: {max_area(heights4)}")

Giải thích code:

1. Hàm max_area(height) nhận danh sách height.
2. left và right được khởi tạo ở hai đầu danh sách. max_water khởi tạo là 0 để lưu trữ diện tích lớn nhất tìm được.
3. Vòng lặp while left < right: tiếp tục chừng nào hai con trỏ chưa gặp hoặc vượt qua nhau.
4. Trong mỗi lần lặp, h = min(height[left], height[right]) tính chiều cao của container (là chiều cao của đường ngắn hơn).
5. w = right - left tính chiều rộng của container (là khoảng cách giữa hai chỉ mục).
6. current_water = h * w tính diện tích của container hiện tại.
7. max_water = max(max_water, current_water) cập nhật max_water nếu diện tích hiện tại lớn hơn.
8. Logic di chuyển con trỏ: if height[left] < height[right]: left += 1 - Nếu đường bên trái ngắn hơn, di chuyển left sang phải. Việc này hy vọng tìm được một đường cao hơn để tăng chiều cao tối thiểu. Ngược lại (else: right -= 1), di chuyển right sang trái.
9. Quá trình lặp lại cho đến khi left và right gặp nhau.
10. Hàm trả về max_water là diện tích container lớn nhất có thể tạo ra.

Độ phức tạp thời gian của giải pháp này là O(n) vì trong mỗi bước lặp, ít nhất một con trỏ di chuyển vào trong, và chúng chỉ di chuyển theo một hướng duy nhất. Độ phức tạp không gian là O(1) vì chúng ta chỉ sử dụng một vài biến phụ.

Tại sao Two Pointers hiệu quả?

Như bạn thấy qua các ví dụ, kỹ thuật Two Pointers mang lại lợi ích đáng kể về hiệu suất:

• Tối ưu hóa thời gian: Hầu hết các bài toán có thể giải bằng Two Pointers thường có giải pháp vét cạn O(n^2). Two Pointers giúp giảm độ phức tạp này xuống O(n) bằng cách loại bỏ các phép so sánh hoặc kiểm tra không cần thiết. Thay vì kiểm tra mọi cặp, chúng ta sử dụng logic di chuyển con trỏ thông minh để chỉ xem xét các cặp có tiềm năng.
• Tối ưu hóa không gian: Nhiều bài toán Two Pointers có thể giải quyết "in-place" hoặc chỉ cần một lượng không gian phụ cố định (O(1)), làm cho chúng trở nên hiệu quả về bộ nhớ, đặc biệt với các tập dữ liệu lớn.

Tuy nhiên, không phải bài toán nào cũng có thể áp dụng Two Pointers. Nó hoạt động tốt nhất khi:

• Dữ liệu có thứ tự (như mảng đã sắp xếp).
• Bài toán liên quan đến việc tìm kiếm cặp/bộ ba phần tử có tính chất nhất định.
• Bài toán liên quan đến việc xử lý các đoạn con (subarray/substring) hoặc loại bỏ trùng lặp.

Hiểu và thành thạo kỹ thuật Two Pointers sẽ trang bị cho bạn một công cụ mạnh mẽ để giải quyết hiệu quả nhiều bài toán phổ biến trong phỏng vấn lập trình và thực tế. Hãy luyện tập với các bài toán khác nhau để nắm vững các mô hình di chuyển con trỏ và khi nào nên áp dụng chúng nhé!