Chuyển tới nội dung chính

Set & Map: ứng dụng giải bài

Bạn sẽ học được gì

Bảng băm không chỉ là lý thuyết — nó là vũ khí giải bài mạnh nhất của người mới. Ba mẫu dùng set/dict dưới đây xuất hiện trong vô số bài tập, và thường hạ độ phức tạp từ O(n²) xuống O(n).

1. Mẫu 1 — set để kiểm tra tồn tại / loại trùng​

"Đã thấy chưa?" là câu hỏi set trả lời tức thì (O(1)). Dùng để phát hiện trùng lặp:

Đang tải trình chạy code…

Cách ngây thơ (hai vòng so từng cặp) là O(n²); dùng set chỉ O(n).

2. Mẫu 2 — dict để đếm tần suất​

"Mỗi thứ xuất hiện bao nhiêu lần?" → dict đếm, một lần duyệt:

Đang tải trình chạy code…

3. Mẫu 3 — dict tra cứu bù (two-sum)​

Bài kinh điển: tìm hai phần tử cộng lại bằng target, trả về chỉ số. Mẹo: với mỗi x, hỏi "đã gặp target - x chưa?" — lưu giá trị → chỉ số trong dict.

🐞 two-sum: A=[2,7,11], target=9Bước 1/5
1def two_sum(A, target):
2  da_thay = {}            # gia tri -> chi so
3  for i, x in enumerate(A):
4      bu = target - x
5      if bu in da_thay:
6          return [da_thay[bu], i]
7      da_thay[x] = i
8  return None
Biến tại bước này
da_thay{}
👉 dict rỗng: sẽ nhớ giá trị → chỉ số.

So với thử mọi cặp O(n²), two-sum bằng dict chỉ O(n) — đây là một trong những mẫu được hỏi nhiều nhất khi phỏng vấn.

4. Mẫu 4 — dict để nhóm (group by)​

Nhóm các phần tử theo một khóa chung (vd nhóm từ theo "dạng đã sắp xếp" để tìm anagram):

Đang tải trình chạy code…

5. Bảng tổng kết mẫu​

Câu hỏi của bàiCông cụĐộ phức tạp
"Đã gặp chưa / có trùng không?"setO(n)
"Mỗi thứ bao nhiêu lần?"dict đếmO(n)
"Tìm cặp/phần bù?"dict giá trị→chỉ sốO(n)
"Nhóm theo đặc điểm chung?"dict nhómO(n)

Quy tắc vàng: thấy mình duyệt đi duyệt lại để tìm/đếm → thử thay bằng set/dict để hạ O(n²) → O(n). Đây là kỹ năng tăng tốc số 1 cho người mới.

6. Mẫu nhận diện​

  • "Trùng lặp", "duy nhất", "đã thấy" → set.
  • "Đếm", "tần suất", "phổ biến nhất" → dict đếm.
  • "Hai phần tử thỏa quan hệ" (tổng, hiệu) → dict tra cứu bù.
  • "Gom nhóm theo đặc điểm" → dict nhóm.

7. 🎮 Trò chơi: Chọn công cụ băm​

🎮 Set hay dict?Câu 1/4· Điểm 0· 🔥 0

set: có/không, loại trùng. dict: đếm, ánh xạ khóa→giá trị, tra cứu bù.

Tìm hai số cộng lại bằng target, trả về chỉ số.

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Mẹo chung để hạ O(n²) xuống O(n) trong bài tìm/đếm là?
2. two-sum bằng dict lưu gì?
3. Để loại phần tử trùng trong một danh sách, cách nhanh nhất?

9. Hoàn thành — XONG Chương 2.4! 🎉​

…

☑️ Hết Chương 2.4 (Bảng băm). Tiếp theo: 2.5.1 — Cây & cây nhị phân.