Thuật toán Python

Bài toán Two Sum trong Python

Tìm hai số có tổng bằng giá trị đích chỉ trong một lần duyệt, dùng dictionary để nhớ những gì đã gặp.

  • Trung cấp
  • Đọc trong 2 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • Phần bù target - value
  • Lưu giá trị đã gặp trong dict
  • O(n) thay vì O(n²)
[2, 7, 11, 15], target 9
chỉ số 0: 2cần 7, chưa gặp → seen = {2: 0}
chỉ số 1: 7cần 2, đã gặp ở 0 → [0, 1]

Tìm người bạn còn thiếu

Vấn đề

Cho một list giá tiền và một ngân sách, hai món nào cộng lại đúng bằng ngân sách? Thử mọi cặp thì được nhưng tốn khoảng n² / 2 lần so sánh. Ghi nhớ những gì đã gặp giúp giải xong chỉ trong một lượt duyệt.

Hình dung đời thường

Two Sum giống đi mua sắm với một số tiền phải tiêu vừa khít. Với mỗi bảng giá, bạn tính xem còn thiếu bao nhiêu, rồi xem lại ghi chú: mình đã gặp món nào có đúng giá đó chưa? Nếu rồi thì đã tìm ra cặp. Nếu chưa, bạn ghi lại giá này cùng vị trí của nó rồi đi tiếp.

Từ việc mua sắm vừa khít số tiền đến code
complement = target - value🤔 Số tiền còn thiếu
if complement in seen:📋 Giá đó đã có trong ghi chú chưa?
return [seen[complement], index]🛍️ Tìm ra cặp: vị trí của cả hai
seen[value] = index✍️ Ghi lại giá này và vị trí của nó, rồi đi tiếp
Tra số tiền còn thiếu thay vì thử mọi cặp.
Định nghĩa ngắn gọn

Bài toán Two Sum yêu cầu tìm vị trí của hai số trong list có tổng bằng một giá trị cho trước. Dùng dictionary lưu các giá trị đã gặp, ta giải được bài toán trong một lượt duyệt, với thời gian O(n).

Những điểm quan trọng

  1. complement = target - value là giá trị còn thiếu để đủ cặp.
  2. seen lưu mỗi giá trị đã duyệt kèm vị trí của nó, nên tra cứu rất nhanh.
  3. if complement in seen: tìm bạn ghép trong số các giá trị đứng trước.
  4. seen[value] = index chạy sau bước kiểm tra, nên một giá trị không bao giờ tự ghép với chính nó.
  5. Với tổng 9, giá trị 7 tìm thấy bạn ghép 2 ở vị trí 0, cho kết quả [0, 1].

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

  • Tìm các cặp có tổng hoặc hiệu cho trước.
  • Học cách đổi bộ nhớ lấy tốc độ bằng bảng băm (hash table).
  • Câu hỏi phỏng vấn rất phổ biến và là nền của 3-Sum cùng các bài tương tự.

Khi nào chưa cần

  • Dữ liệu đã sắp xếp và bộ nhớ hạn chế: hai con trỏ từ hai đầu không cần thêm bộ nhớ.
  • Cần mọi cặp chứ không chỉ một: gom kết quả thay vì trả về ngay ở cặp đầu tiên.

Code ví dụ

Chạy code →
main.py
def two_sum(values, target):
    seen = {}
    for index, value in enumerate(values):
        complement = target - value
        if complement in seen:
            return [seen[complement], index]
        seen[value] = index
    return []

print(two_sum([2, 7, 11, 15], 9))
Lấy nút Run cho ví dụ này

Kết quả khi chạy

[0, 1]

Giải thích code

Dictionary seen lưu các giá trị đã duyệt cùng vị trí của chúng. Với mỗi phần tử, chương trình tính phần bù complement = target - value và kiểm tra xem phần bù đã có trong seen chưa. Vì tra cứu trong dictionary chỉ mất O(1), cả thuật toán chạy trong O(n) và cần thêm O(n) bộ nhớ.

Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.

Bài tập mở rộng

Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.

  1. Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
  2. In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
  3. Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Chạy trong trình biên dịch Python →

Lỗi hay gặp

Lưu trước rồi mới kiểm tra

Một giá trị có thể tự ghép với chính nó, như 3 + 3 = 6 khi chỉ có một số 3.

Sai
seen[value] = index
if target - value in seen:
Cách sửa
if target - value in seen:
    return [seen[target - value], index]
seen[value] = index

Bạn học xong bài này chưa?

Đánh dấu đã học để theo dõi tiến độ của bạn.

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Tất cả thử thách