Mô phỏng thuật toán Bộ ba tổng 0 (3Sum)

3Sum · Nhóm: Hai con trỏ

Bộ ba tổng 0 trên mảng đã sắp: cố định lần lượt một số rồi dùng hai con trỏ quét cặp còn lại, hạ từ O(n³) xuống O(n²).

Ý tưởng

Với mỗi i, cố định a[i] và đặt hai con trỏ L = i + 1, R = n − 1 tiến vào giữa.

Tổng bằng 0 thì ghi bộ ba rồi dời cả L và R; tổng nhỏ quá thì L tiến sang phải để tăng tổng; lớn quá thì R lùi sang trái để giảm tổng.

Vì sao đúng

Vì mảng đã sắp nên khi tổng lệch ta biết ngay phải kéo con trỏ nào; mỗi số cố định chỉ quét cặp một lượt O(n), tổng thể O(n²).

Mã Python

def three_sum(a):            # a is sorted ascending
    n, res = len(a), []
    for i in range(n - 2):   # fix a[i]
        L, R = i + 1, n - 1  # two pointers inward
        while L < R:
            s = a[i] + a[L] + a[R]
            if s == 0:
                res.append((a[i], a[L], a[R]))
                L += 1; R -= 1
            elif s < 0:
                L += 1        # need a larger sum
            else:
                R -= 1        # need a smaller sum
    return res

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.