Hai con trỏ: bỏ qua những cặp chắc chắn không cần xét

Lan có 100 000 thẻ số và muốn tìm hai thẻ khác nhau có tổng bằng 50. Thử từng cặp cần gần 5 tỉ lần kiểm tra. Lan sắp xếp thẻ theo giá trị rồi đặt một ngón tay ở mỗi đầu. Mỗi lần so sánh giúp bạn bỏ qua nhiều cặp mà vẫn giữ cơ hội tìm được đáp án.

Một bước đúng phải loại được cả nhóm lựa chọn

Hai con trỏ (two pointers) là kỹ thuật giữ hai vị trí để xét dữ liệu có trật tự. Tên gọi không bảo đảm chương trình nhanh hoặc đúng. Bạn cần giải thích những lựa chọn nào bị bỏ qua sau mỗi lần di chuyển.

Giả sử dãy a tăng dần và cần tìm hai vị trí khác nhau có tổng bằng target. Đặt left = 0, right = len(a) - 1. Nếu tổng nhỏ hơn target, ngay cả phần tử lớn nhất còn lại cũng không ghép đủ với a[left]. Vì vậy mọi cặp còn lại chứa left đều quá nhỏ; ta tăng left.

Nếu tổng lớn hơn target, ngay cả phần tử nhỏ nhất còn lại cũng làm a[right] quá lớn. Mọi cặp còn lại chứa right đều quá lớn; ta giảm right. Nếu bằng, hai vị trí hiện tại là đáp án. Từng lần bỏ một hàng hoặc một cột cặp đều có lý do.

Ban đầu 1 + 10 = 11, nên không cặp nào chứa 1 đạt tổng 12. Tiếp theo 3 + 10 = 13, nên không cặp nào còn lại chứa 10 đạt tổng 12. Sau đó 3 + 8 = 11, nên bỏ 3. Cuối cùng 4 + 8 = 12, ta tìm được cặp.

Đoạn mã sau chạy đúng quá trình đó và in từng trạng thái:

a = [1, 3, 4, 6, 8, 10]
target = 12
left, right = 0, len(a) - 1
while left < right:
    total = a[left] + a[right]
    print(left, right, total)
    if total == target:
        print("Tìm thấy", a[left], a[right])
        break
    if total < target:
        left += 1
    else:
        right -= 1

0 5 11
1 5 13
1 4 11
2 4 12
Tìm thấy 4 8

Điều kiện left < right bắt buộc hai vị trí khác nhau. Hai giá trị bằng nhau vẫn được phép ghép nếu chúng ở hai vị trí. Khi hai con trỏ gặp nhau, không còn cặp chưa xét. Nếu hết vòng mà chưa tìm thấy, đáp án là không tồn tại.

Bất biến cho thấy không bỏ sót đáp án

Bất biến vòng lặp (loop invariant) là điều đúng ở đầu mỗi vòng. Ở đây, nếu một cặp đáp án chưa được tìm thấy thì nó nằm trong khoảng chỉ số từ left đến right. Ban đầu khoảng này chứa toàn bộ dãy. Khi tổng quá nhỏ, cặp chứa left không thể là đáp án nên bỏ đầu trái vẫn giữ bất biến. Lập luận đối xứng áp dụng khi tổng quá lớn.

Mỗi vòng tăng left hoặc giảm right, nên khoảng giữa chúng ngắn đi ít nhất một. Có tối đa n - 1 lần dịch trên dãy có n phần tử. Phần quét tốn O(n) thời gian và O(1) bộ nhớ phụ. Nếu đầu vào chưa tăng, cần sắp xếp trước; tổng thời gian là O(n log n).

Chương trình sau đọc dãy chưa sắp xếp, in YES nếu có hai vị trí thỏa điều kiện và NO nếu không:

6 12
8 1 10 4 3 6

import sys
data = list(map(int, sys.stdin.read().split()))
n, target = data[0], data[1]
a = sorted(data[2:2 + n])
left, right = 0, n - 1
found = False
while left < right:
    total = a[left] + a[right]
    if total == target:
        found = True
        break
    if total < target:
        left += 1
    else:
        right -= 1
print("YES" if found else "NO")

YES

Nếu đề yêu cầu chỉ số ban đầu, không thể in chỉ số sau khi sắp xếp như thể chúng không đổi. Hãy sắp xếp các cặp (giá trị, chỉ số ban đầu) và trả lại chỉ số đi kèm. Nếu đề chỉ hỏi tồn tại hoặc số lượng, sắp xếp các giá trị là đủ.

Đoạn sau cho thấy hai số bằng nhau có thể hợp lệ, còn một số đơn lẻ thì không:

def has_pair(a, target):
    a = sorted(a)
    left, right = 0, len(a) - 1
    while left < right:
        total = a[left] + a[right]
        if total == target:
            return True
        if total < target:
            left += 1
        else:
            right -= 1
    return False

print(has_pair([5, 5], 10))
print(has_pair([5], 10))
print(has_pair([-7, -2, 4, 9], 2))

True
False
True

Số âm không phá vỡ lập luận của thuật toán này. Điều cần thiết là thứ tự tăng, không phải mọi giá trị đều dương. Ví dụ thứ ba có cặp -7 và 9. Hàm không sửa danh sách gốc vì sorted tạo một danh sách mới.

Đếm cả một hàng cặp khi tổng không vượt ngưỡng

Giờ hãy đếm cặp chỉ số i < j thỏa a[i] + a[j] <= limit. Dãy vẫn tăng. Nếu a[left] + a[right] <= limit, mọi phần tử từ left + 1 đến right ghép được với left. Có đúng right - left cặp như vậy.

Ta cộng cả nhóm rồi tăng left. Mỗi cặp được tính đúng một lần, tại lúc chỉ số trái của nó bị đưa ra khỏi khoảng. Nếu tổng hai đầu quá lớn, không chỉ số còn lại nào ghép được với right, nên giảm right mà không cộng. Các cặp chứa chỉ số đã bỏ đều đã được tính hoặc chứng minh không hợp lệ.

Chương trình dưới đây đếm cặp vị trí, kể cả khi các giá trị trùng nhau:

def count_at_most(values, limit):
    a = sorted(values)
    left, right = 0, len(a) - 1
    count = 0
    while left < right:
        if a[left] + a[right] <= limit:
            count += right - left
            left += 1
        else:
            right -= 1
    return count

print(count_at_most([7, 1, 4, 2], 8))
print(count_at_most([2, 2, 2, 2], 4))
print(count_at_most([-3, -1, 2, 5], 0))

4
6
2

Bốn số 2 tạo ra sáu cặp vị trí, dù mọi cặp có cùng giá trị. Nếu đề yêu cầu cặp giá trị phân biệt, phải định nghĩa lại cách đếm. Với n = 100 000, số cặp có thể lên tới 4 999 950 000. Python hỗ trợ số nguyên lớn, nhưng cần cẩn thận nếu chuyển thuật toán sang ngôn ngữ có kiểu số nguyên cố định.

Đếm tổng trong một khoảng bằng hiệu hai lần đếm

Giả sử cần đếm cặp có tổng từ low đến high, kể cả hai đầu. Đếm tất cả cặp có tổng không quá high, rồi trừ số cặp có tổng nhỏ hơn low. Vì các phần tử là số nguyên, điều kiện sau tương đương tổng không quá low - 1.

Đoạn mã sau minh họa phép trừ trên dãy có số âm và giá trị trùng:

def at_most(a, limit):
    left, right, count = 0, len(a) - 1, 0
    while left < right:
        if a[left] + a[right] <= limit:
            count += right - left
            left += 1
        else:
            right -= 1
    return count

a = sorted([-2, 0, 2, 2, 5])
low, high = 2, 4
print(at_most(a, high) - at_most(a, low - 1))

4

Phép trừ này dựa vào tổng nguyên. Với số thực, không thể thay điều kiện nhỏ hơn low bằng không quá low - 1. Bạn cần một hàm đếm riêng với phép so sánh < low. Hai lượt quét vẫn tốn O(n) sau khi sắp xếp.

Hai dãy tăng có thể được quét cùng lúc

Hai con trỏ không nhất thiết đứng trong cùng một dãy. Giả sử a và b đều tăng, bạn muốn liệt kê mỗi giá trị chung một lần. Đặt i và j ở đầu hai dãy. Nếu a[i] < b[j], mọi phần tử chưa xét của b đều không nhỏ hơn b[j]. Do đó a[i] không thể xuất hiện trong phần còn lại của b, nên tăng i.

Nếu a[i] > b[j], lập luận tương tự cho phép tăng j. Nếu bằng nhau, ghi giá trị đó nếu chưa ghi trước đó, rồi tăng cả hai. Giá trị trùng sau đó có thể được gặp lại; kiểm tra phần tử cuối của kết quả giúp tránh ghi lặp.

Đoạn mã này dùng hai danh sách đã tăng và có lặp:

a = [1, 2, 2, 5, 8]
b = [0, 2, 2, 2, 7]
i = j = 0
common = []
while i < len(a) and j < len(b):
    if a[i] < b[j]:
        i += 1
    elif a[i] > b[j]:
        j += 1
    else:
        if not common or common[-1] != a[i]:
            common.append(a[i])
        i += 1
        j += 1
print(common)

[2]

Mỗi con trỏ chỉ đi tới, nên tổng số lần dịch không quá n + m. Phần quét tốn O(n + m) thời gian. Danh sách kết quả cần thêm bộ nhớ theo số giá trị chung. Nếu hai đầu vào chưa được sắp xếp, phải tính thêm thời gian sắp xếp chúng.

Đừng nhầm giao phân biệt với giao có số lần lặp. Chẳng hạn, [2, 2] và [2, 2, 2] có một giá trị chung phân biệt, nhưng ghép tối đa được hai cặp bằng nhau. Đề bài phải nói rõ cần đại lượng nào.

Khoảng cách nhỏ nhất cũng bỏ được một đầu nhỏ

Với hai dãy tăng không rỗng, tìm giá trị nhỏ nhất của abs(a[i] - b[j]). Xét hai phần tử hiện tại. Nếu a[i] < b[j], mọi phần tử phía sau b[j] đều lớn hơn hoặc bằng nó. Giữ a[i] và tăng j không thể cải thiện khoảng cách, nên sau khi ghi nhận khoảng cách hiện tại ta tăng i.

Nếu a[i] > b[j], tăng j theo lý do đối xứng. Nếu hai giá trị bằng nhau, khoảng cách là 0, không thể nhỏ hơn nữa. Các cặp đã loại không thể cải thiện kết quả tốt nhất đã ghi. Khi một dãy hết, mọi cặp còn lại đều đã được loại theo lập luận đó.

a = [-8, 1, 9, 17]
b = [-3, 5, 13]
i = j = 0
best = abs(a[0] - b[0])
while i < len(a) and j < len(b):
    best = min(best, abs(a[i] - b[j]))
    if a[i] < b[j]:
        i += 1
    elif a[i] > b[j]:
        j += 1
    else:
        break
print(best)

4

Khởi tạo từ cặp đầu tiên chỉ hợp lệ khi cả hai dãy không rỗng. Nếu đề cho phép dãy rỗng, cần quy định kết quả riêng trước khi truy cập a[0] hoặc b[0]. Với hai dãy đã tăng có 100 000 phần tử mỗi dãy, phần quét có tối đa khoảng 200 000 lần dịch. Duyệt mọi cặp có thể cần 10 tỉ phép so sánh.

Cố định một số rồi tìm hai số còn lại

Bài ba tổng (3-sum) hỏi có ba vị trí khác nhau mà tổng bằng target hay không. Trước hết sắp xếp dãy. Chọn một vị trí fixed, rồi tìm hai số có tổng bằng target - a[fixed] ở phía bên phải. Hai con trỏ bắt đầu tại fixed + 1 và cuối dãy.

Mỗi bộ ba vị trí có đúng một vị trí nhỏ nhất trong thứ tự đã sắp xếp. Lượt chọn vị trí đó sẽ xét phần chứa hai vị trí còn lại. Lập luận loại cả hàng hoặc cột cặp bảo đảm lượt quét không bỏ sót cặp cần tìm. Điều kiện left < right bảo đảm ba vị trí khác nhau.

def has_three(values, target):
    a = sorted(values)
    for fixed in range(len(a) - 2):
        left, right = fixed + 1, len(a) - 1
        while left < right:
            total = a[fixed] + a[left] + a[right]
            if total == target:
                return True
            if total < target:
                left += 1
            else:
                right -= 1
    return False

print(has_three([-4, -1, 0, 2, 5], 1))
print(has_three([2, 2], 6))
print(has_three([2, 2, 2], 6))

True
False
True

Có tối đa n lượt chọn fixed, mỗi lượt quét tối đa n bước. Sau sắp xếp, thời gian là O(n²) và bản sao đã sắp xếp dùng O(n) bộ nhớ. Với n = 2 000, cỡ vài triệu bước có thể phù hợp tùy giới hạn máy. Với n = 100 000, cỡ 10 tỉ bước là quá lớn; không nên mặc định cách này đủ nhanh.

Đoạn trên chỉ hỏi tồn tại, nên không cần bỏ các giá trị trùng. Nếu đề yêu cầu liệt kê bộ ba giá trị phân biệt, phải bỏ lặp một cách có chủ đích. Nếu đề đếm bộ ba chỉ số, bỏ lặp tùy tiện sẽ làm mất đáp án.

Hai con trỏ và cửa sổ trượt trả lời câu hỏi khác nhau

Ở bài tìm cặp, hai con trỏ biểu diễn hai phần tử được chọn. Những phần tử giữa chúng không nhất thiết thuộc đáp án. Trong cửa sổ trượt (sliding window), hai biên biểu diễn một đoạn liên tiếp và chương trình duy trì trạng thái của cả đoạn. Cửa sổ trượt là một cách dùng hai con trỏ, nhưng không phải mọi bài hai con trỏ đều là cửa sổ.

Với tổng đoạn không vượt ngưỡng, số không âm giúp tổng không giảm khi mở rộng bên phải. Nếu có số âm, một đoạn đang vượt ngưỡng có thể trở lại hợp lệ khi thêm phần tử âm. Quy tắc dịch biên vì vậy phải được chứng minh lại. Bài 15 đi sâu vào cửa sổ trượt; ở đây ta chỉ phân biệt đối tượng mà các con trỏ mô tả.

Một phép duyệt thô trên dữ liệu nhỏ là cách tốt để kiểm tra hàm đếm cặp. Đoạn sau so sánh hai cách trên một dãy có âm và trùng:

a = [-2, 0, 2, 2, 5]
limit = 3
slow = sum(a[i] + a[j] <= limit
           for i in range(len(a))
           for j in range(i + 1, len(a)))
left, right, fast = 0, len(a) - 1, 0
while left < right:
    if a[left] + a[right] <= limit:
        fast += right - left
        left += 1
    else:
        right -= 1
print(slow, fast, slow == fast)

6 6 True

Hai cách cần cho cùng kết quả. Phép duyệt thô xét n(n - 1) / 2 cặp, nên chỉ thích hợp làm đối chứng trên dữ liệu nhỏ. Bạn có thể thử thêm dãy một phần tử, toàn số bằng nhau, hoặc ngưỡng nhỏ hơn mọi tổng. Kết quả bằng nhau trên vài ví dụ chưa thay thế chứng minh, nhưng giúp phát hiện lỗi cài đặt.

Trước khi chọn thuật toán, bạn hãy ghi rõ đáp án cần tính theo vị trí hay theo giá trị. Sau đó kiểm tra điều kiện sắp xếp và ràng buộc kích thước. Một lời giải nhanh nhưng dùng sai đối tượng để đếm vẫn cho kết quả sai.

Lỗi thường gặp

Tóm tắt

• Hai đầu của dãy tăng giúp loại một nhóm cặp sau mỗi phép so sánh.
• Đếm cặp tổng không quá ngưỡng bằng cách cộng right - left khi cả nhóm hợp lệ.
• Hai dãy tăng cho phép quét đồng thời trong O(n + m) sau khi sắp xếp.
• Cố định một phần tử và quét phần còn lại cho bài ba tổng trong O(n²).
• Cần tính chi phí sắp xếp và xác định đáp án tính theo giá trị hay vị trí.

Kiểm tra nhanh

Đọc thêm

• Python: Sắp xếp danh sách
• Python: Kiểu danh sách