Two sum bằng Python: tìm hai số có tổng bằng k
Bài 2/10 · Chương 25
Bài tập phỏng vấn Python
- 9 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 11
Bài toán two sum hỏi: trong một list số, hai số nào có tổng bằng đúng một số k cho trước. Trang này giải two sum bằng Python theo từng bước, từ cách thử mọi cặp tới cách dùng dict chỉ đi qua list một lượt, rồi cho bạn một bài tập được chấm ngay trên trang.
Cần biết trước: vòng lặp lồng nhau, dict và độ phức tạp Big O.
Đề bài
Thu Hà có một phiếu quà tặng 64.000 đ, dùng cho đúng hai ly trên hóa đơn của bàn. Hóa đơn là list giá từng ly, theo thứ tự gọi món:
hoa_don = [29000, 45000, 32000, 35000, 29000, 32000]
phieu = 64000
print(len(hoa_don), "ly, phiếu", phieu)KẾT QUẢ
6 ly, phiếu 64000Viết hàm cap_ly(ds, k) trả về chỉ số (i, j) của hai ly có tổng giá bằng k, với i < j. Không có cặp nào thì hàm trả về None. Một ly không được tính hai lần, nhưng hai ly cùng giá ở hai chỉ số khác nhau thì được.
Hóa đơn trên có ba cặp hợp lệ: (0, 3), (3, 4) và (2, 5). Để mọi lời giải cho cùng một đáp án, đề chốt luật chọn: lấy cặp mà ly thứ hai đứng sớm nhất trong hóa đơn, tức j nhỏ nhất; cùng j thì lấy i nhỏ nhất. Đáp án ở đây là (0, 3).
Cách 1: thử mọi cặp bằng hai vòng lặp
Cách đầu tiên ai cũng nghĩ ra là thử từng cặp. Vòng ngoài chạy j, vòng trong chạy mọi i đứng trước j, nên cặp đầu tiên tìm thấy chính là cặp có j nhỏ nhất:
def cap_ly(ds, k):
for j in range(len(ds)):
for i in range(j):
if ds[i] + ds[j] == k:
return i, j
return None
hoa_don = [29000, 45000, 32000, 35000, 29000, 32000]
print(cap_ly(hoa_don, 64000))
print(cap_ly(hoa_don, 77000))
print(cap_ly(hoa_don, 100000))KẾT QUẢ
(0, 3)
(1, 2)
Nonerange(j) dừng trước j, nên i không bao giờ bằng j và một ly không cặp với chính nó. return đặt trong vòng trong dừng cả hàm ngay khi gặp cặp đầu tiên. Dòng return None chỉ chạy khi hai vòng đã thử hết mà không thấy cặp nào. Đổi 77000 thành 61000 rồi chạy lại: hàm in (0, 2), cặp cà phê sữa và bạc xỉu.
Vì sao cách hai vòng lặp chậm
Với hóa đơn sáu ly thì cách nào cũng xong ngay. Người phỏng vấn sẽ hỏi tiếp: list có một triệu phần tử thì sao? Muốn trả lời, bạn đếm số phép cộng mà hàm làm khi không có cặp nào, trường hợp hàm phải thử hết:
def dem_buoc(ds, k):
buoc = 0
for j in range(len(ds)):
for i in range(j):
buoc += 1
if ds[i] + ds[j] == k:
return buoc
return buoc
for n in [10, 100, 1000]:
print(n, "ly:", dem_buoc([29000] * n, 1), "phép cộng")KẾT QUẢ
10 ly: 45 phép cộng
100 ly: 4950 phép cộng
1000 ly: 499500 phép cộngList dài gấp 10 lần thì số phép cộng tăng khoảng 100 lần: đúng bằng n * (n - 1) // 2, số cặp có thể có. Cách viết Big O gọi đó là O(n²). Một triệu ly sẽ cần khoảng 500 tỉ phép cộng. Chỗ phí công nằm ở vòng trong: với mỗi ly, nó dò lại từ đầu những ly đã đi qua, dù vòng ngoài đã nhìn thấy chúng rồi.
Cách 2: nhớ các số đã gặp trong dict
Đứng ở ly giá gia, bạn chỉ cần đúng một giá: k - gia. Câu hỏi đổi thành "giá k - gia đã xuất hiện ở trước chưa, ở chỉ số nào?". Một dict từ giá sang chỉ số trả lời câu đó bằng một lần tra, vì toán tử in trên dict thường không phải dò từng khóa. Chạy từng bước để xem dict da_gap lớn dần cho tới lúc tìm thấy cặp:
hoa_don = [29000, 45000, 32000, 35000]
phieu = 64000
da_gap = {}
for j, gia in enumerate(hoa_don):
if phieu - gia in da_gap:
print("Tìm thấy:", da_gap[phieu - gia], j)
break
da_gap[gia] = jKẾT QUẢ
Tìm thấy: 0 3Tới ly thứ tư (35000), giá còn thiếu là 29000, đã nằm trong dict với chỉ số 0. Viết thành hàm, thêm một điều kiện: chỉ ghi giá vào dict khi giá đó chưa có, để dict giữ chỉ số đầu tiên của mỗi giá:
def cap_ly(ds, k):
da_gap = {}
for j, gia in enumerate(ds):
can_tim = k - gia
if can_tim in da_gap:
return da_gap[can_tim], j
if gia not in da_gap:
da_gap[gia] = j
return None
hoa_don = [29000, 45000, 32000, 35000, 29000, 32000]
print(cap_ly(hoa_don, 64000))
print(cap_ly(hoa_don, 77000))
print(cap_ly(hoa_don, 100000))KẾT QUẢ
(0, 3)
(1, 2)
NoneHàm đi qua list đúng một lượt, mỗi lượt một lần tra và nhiều nhất một lần ghi, nên số bước thường tăng cùng nhịp với n: O(n). Cái giá phải trả là bộ nhớ cho dict, tối đa n cặp. Hai cách trả về cùng đáp án vì cả hai đều dừng ở j nhỏ nhất. enumerate() cho cả chỉ số và giá ở mỗi lượt lặp, nên không cần ds[j].
Thứ tự hai dòng tra và ghi là quyết định quan trọng của cách 2. Dòng if gia not in da_gap: là quyết định thứ hai: bỏ nó đi thì hàm vẫn tìm ra một cặp đúng tổng, nhưng có thể sai luật chọn của đề.
Luật chọn cặp là của riêng trang này. Đề gốc thường nói "có đúng một cặp", và khi đó dòng if gia not in da_gap: không cần.
Nói gì với người phỏng vấn
Trước khi viết code, hỏi lại đề: "Nếu có nhiều cặp thì trả về cặp nào? Có luôn có lời giải không?". Trang này đã phải chốt luật chọn cặp ở mục Đề bài. Ở buổi phỏng vấn, đó là câu bạn hỏi đầu tiên.
Viết code xong, bạn trình bày trong bốn câu, theo thứ tự cách chậm và giá của nó, cách nhanh, bộ nhớ, trường hợp biên:
"Thử mọi cặp cần khoảng
n * n / 2phép cộng, tức O(n²).""Tôi đi một lượt. Với mỗi số, số cần tìm là
ktrừ nó, và tôi tra số đó trong một dict giữ chỉ số đầu tiên của các số đã gặp, nên tổng số bước thường là O(n).""Đổi lại, dict tốn thêm bộ nhớ cho tối đa
nphần tử.""Tôi đã xét list rỗng, không có cặp nào, hai số bằng nhau ở hai chỉ số khác nhau, và một số bằng nửa
kkhông được cặp với chính nó."
Nếu người phỏng vấn cho list đã sắp xếp, hãy nói thêm rằng khi đó có cách dùng hai chỉ số đi từ hai đầu vào giữa, không cần dict.
Kiểm tra nhanh
Hóa đơn có 20 ly và không có cặp nào vừa hết phiếu. Hàm
dem_buoccủa mục "Vì sao cách hai vòng lặp chậm" làm bao nhiêu phép cộng?Trong cách 2, vì sao dòng tra
k - gia in da_gapphải đứng trước dòng ghida_gap[gia] = j?- Để dict giữ chỉ số đầu tiên của mỗi giá
- Để một ly giá bằng nửa phiếu không cặp với chính nó
- Để hàm dừng sớm hơn khi tìm thấy cặp
Câu cuối của phần trình bày cần nêu những trường hợp biên nào?
- List rỗng
- Không có cặp nào
- Một số bằng nửa
k - List có đúng một triệu phần tử
Bài tập
Đếm số cách dùng phiếu cho hai ly
Quán muốn biết một hóa đơn có bao nhiêu cách chọn hai ly để dùng vừa hết phiếu. Viết hàm dem_cap(ds, k) trả về số cặp chỉ số (i, j), với i < j, mà ds[i] + ds[j] == k. Giá là số nguyên không âm, và hàm không được sửa list ds của nơi gọi hàm.
Trả về: số cặp, một int.
Hai ly cùng giá ở hai chỉ số khác nhau vẫn là hai ly khác nhau.
Một ly không cặp với chính nó.
Trình chấm còn đưa vào một hóa đơn 300 ly và đếm số phép tính (cộng, trừ, so sánh, tra dict) trên các giá: đi qua list một lượt như cách 2 thì qua, thử mọi cặp thì trượt. Ôn lại: dict.
hoa_don = [29000, 45000, 32000, 35000, 29000, 32000]
def dem_cap(ds, k):
pass # Viết thân hàm thay cho dòng nàyCâu hỏi thường gặp
Có cách giải two sum trong Python nào không cần dict không?
Có, khi được phép sắp xếp: đặt hai chỉ số ở hai đầu list đã sắp, tổng nhỏ hơn k thì dời chỉ số trái, lớn hơn thì dời chỉ số phải. Cách này không tốn bộ nhớ thêm nhưng sắp xếp mất O(n log n) và làm mất chỉ số gốc, nên đề hỏi chỉ số thì cách dict hợp hơn. Sắp xếp list nằm ở bài sắp xếp list.
Dùng set thay cho dict được không?
Được nếu đề chỉ hỏi có cặp hay không, hoặc hỏi hai giá: set trả lời "giá còn thiếu đã gặp chưa" cũng bằng một lần tra. Đề hỏi chỉ số thì cần dict, vì set không nhớ giá đó nằm ở đâu. Hai kiểu so sánh với nhau ở bài set.
Khi nào cách hai vòng lặp vẫn chấp nhận được?
Khi list ngắn và chỉ chạy một lần, như hóa đơn một bàn: vài chục phép cộng không đáng để thêm một dict. Ở buổi phỏng vấn, bạn vẫn nên viết cách hai vòng lặp trước nếu chưa nghĩ ra cách nhanh, rồi nói rõ nó là O(n²) và cải tiến từ đó.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.