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.
- Phần bù target - value
- Lưu giá trị đã gặp trong dict
- O(n) thay vì O(n²)
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.
complement = target - value🤔 Số tiền còn thiếuif complement in seen:📋 Giá đó đã có trong ghi chú chưa?return [seen[complement], index]🛍️ Tìm ra cặp: vị trí của cả haiseen[value] = index✍️ Ghi lại giá này và vị trí của nó, rồi đi tiếpBà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
complement = target - valuelà giá trị còn thiếu để đủ cặp.seenlưu mỗi giá trị đã duyệt kèm vị trí của nó, nên tra cứu rất nhanh.if complement in seen:tìm bạn ghép trong số các giá trị đứng trước.seen[value] = indexchạ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ó.- 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ụ
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))
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.
- 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.
- In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
- Đ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.
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.
seen[value] = index
if target - value in seen:
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