Đây là bản xem thử. Phiên bản đầy đủ trong ứng dụng có bài tập, AI chấm ngay và theo dõi tiến độ học.
Bài học
Hai con trỏ trên dãy đơn điệu
Mục tiêu bài học
Lớp 10 em đã quen tìm kiếm nhị phân và duyệt mảng một lượt O(n). Bài này đi xa hơn: khi mảng đã sắp xếp hoặc có tính đơn điệu, hai chỉ số chạy cùng lúc — mỗi chỉ số chỉ tăng, không bao giờ lùi — có thể thay thế cả một vòng lặp lồng O(n²). Học xong, em tự thiết kế và **chứng minh** được một lời giải hai con trỏ, không chỉ bắt chước khuôn mẫu.
Cần nhớ trước
Cần trước: duyệt mảng một chiều, so sánh và sắp xếp cơ bản (Tin 10), tìm kiếm nhị phân trên mảng đã sắp xếp (Chương 1, Khóa 1 của lớp 11 này). Bài không nhắc lại cú pháp for/while — em cần thành thạo rồi mới học tiếp phần này.
Bài chuẩn và bài HSG cùng chủ đề
Đề chuẩn thường dừng ở mức: cho mảng đã sắp xếp, tìm xem có tồn tại hai phần tử tổng bằng S hay không — nested loop hai lớp, O(n²), n nhỏ thì chạy kịp. Đề HSG đẩy xa hơn theo hai hướng: (1) ràng buộc n lớn (10⁵ trở lên) khiến O(n²) chắc chắn timeout, buộc phải hạ xuống O(n); (2) đề còn yêu cầu **đếm** số cặp thỏa điều kiện, hoặc mở rộng sang ba phần tử — không còn là bài tra cứu tồn tại/không tồn tại đơn giản.
Bài toán mở đầu
Cho mảng `a` gồm n số nguyên, đã sắp xếp không giảm, và một số S. Tìm hai chỉ số i < j sao cho a[i] + a[j] = S. Nếu duyệt mọi cặp, độ phức tạp là O(n²) — với n = 10⁵ thì khoảng 10¹⁰ phép so sánh, vượt xa giới hạn một giây chấm bài. Mảng đã sắp xếp — thông tin đó phải được tận dụng, không thể bỏ phí.
Ý tưởng chính: hai con trỏ ngược chiều
Đặt lo = 0 ở đầu mảng, hi = n − 1 ở cuối mảng. Xét tổng a[lo] + a[hi]. Nếu tổng đúng bằng S, xong. Nếu tổng **nhỏ hơn** S, phải tăng tổng lên — mà a[hi] đã là phần tử lớn nhất còn lại trong đoạn đang xét, nên cách duy nhất để tăng tổng là dịch lo sang phải, lấy một a[lo] lớn hơn. Ngược lại nếu tổng **lớn hơn** S, dịch hi sang trái. Mỗi bước, đúng một trong hai con trỏ tiến vào trong; vòng lặp dừng khi lo ≥ hi. Tổng số bước tối đa là n, nên độ phức tạp là O(n).
Vì sao cách di chuyển này không bỏ sót cặp nghiệm
Đây là chỗ học sinh hay tin mà không chứng minh. Giả sử tại một bước a[lo] + a[hi] < S và ta quyết định tăng lo. Cần chỉ ra: không cặp nào chứa hi hiện tại và một chỉ số nhỏ hơn lo bị bỏ lỡ. Thật vậy, với mọi lo' < lo, vì mảng không giảm nên a[lo'] ≤ a[lo], suy ra a[lo'] + a[hi] ≤ a[lo] + a[hi] < S — cặp (lo', hi) chắc chắn không đạt tổng S, nên bỏ qua toàn bộ các lo' đó là an toàn. Lập luận đối xứng áp dụng khi tổng lớn hơn S và ta giảm hi. Đây chính là phần "chứng minh đúng đắn" mà đề viết HSG luôn đòi hỏi, không chỉ code chạy ra kết quả đúng trên vài test.
Mỗi bước chỉ một con trỏ di chuyển — tổng số lần dịch chuyển của cả hai con trỏ không vượt quá n.
Ví dụ
Ví dụ 1 — Tìm cặp có tổng bằng S bằng hai con trỏ ngược chiều
1
Cho mảng đã sắp xếp a = [1, 3, 5, 8, 12, 16, 19, 22] (n = 8) và S = 27. Tìm một cặp chỉ số (i, j) sao cho a[i] + a[j] = 27.
2
lo = 0 (a[lo] = 1), hi = 7 (a[hi] = 22). Ta có tổng a[0] + a[7] = 1 + 22 = 23 < 27, nên theo lập luận ở trên, tăng lo.
3
lo = 1 (a[lo] = 3), hi = 7 (a[hi] = 22): tổng = 3 + 22 = 25 < 27. Vẫn nhỏ hơn S nên tiếp tục tăng lo.
4
lo = 2 (a[lo] = 5), hi = 7 (a[hi] = 22): tổng = 5 + 22 = 27 = S. Vậy cặp (i, j) = (2, 7), tức a[2] = 5 và a[7] = 22, thỏa mãn.
5
def two_sum_sorted(a, S):
lo, hi = 0, len(a) - 1
while lo < hi:
s = a[lo] + a[hi]
if s == S:
return (lo, hi)
elif s < S:
lo += 1
else:
hi -= 1
return None # không có cặp nào thỏa
assert two_sum_sorted([1, 3, 5, 8, 12, 16, 19, 22], 27) == (2, 7)
6
Với mảng rỗng, `lo=0, hi=-1`, vòng lặp không chạy lần nào, hàm trả về None ngay — đúng, không có cặp nào. Với mảng chỉ một phần tử, `lo=hi=0`, điều kiện `lo<hi` sai ngay, cũng trả về None — đúng, một phần tử không tạo được cặp. Vậy cặp duy nhất cho ví dụ trên là (5, 22), tại chỉ số (2, 7), độ phức tạp O(n).
Bước 1: lo=0, hi=7, tổng 1+22=23 < 27 nên tăng lo.Bước 3: lo=2, hi=7, tổng 5+22=27=S — tìm thấy cặp, dừng thuật toán.
Mở rộng: hai con trỏ cùng chiều
Hai con trỏ ngược chiều xử lý bài toán "tìm một cặp". Khi bài toán là **gộp hai dãy đã sắp xếp thành một dãy sắp xếp**, hai con trỏ chạy **cùng chiều** (đều chỉ tiến, không bao giờ đổi hướng) mới là kỹ thuật đúng — mỗi bước so sánh phần tử đang trỏ tới của hai dãy, lấy phần tử nhỏ hơn, rồi tiến con trỏ tương ứng. Đây chính là bước "trộn" (merge) sẽ dùng lại nguyên vẹn trong thuật toán sắp xếp trộn ở Khóa 5 (chia để trị).
Ví dụ
Ví dụ 2 — Trộn hai dãy đã sắp xếp bằng hai con trỏ cùng chiều
1
Gộp a = [2, 5, 9, 14] và b = [1, 3, 8, 20, 25] (cả hai đã sắp xếp tăng dần) thành một dãy tăng dần duy nhất, không dùng hàm sort có sẵn.
2
Hai chỉ số i (trên a), j (trên b), cả hai bắt đầu tại 0. Mỗi bước so sánh a[i] và b[j], ghi phần tử nhỏ hơn (hoặc bằng) ra kết quả rồi tiến chỉ số của dãy vừa lấy. Khi một dãy hết phần tử, chép nốt phần còn lại của dãy kia — phần đó đã sắp xếp sẵn nên không cần so sánh gì thêm.
3
```python
def merge_sorted(a, b):
i = j = 0
out = []
while i < len(a) and j < len(b):
if a[i] <= b[j]:
out.append(a[i]); i += 1
else:
out.append(b[j]); j += 1
out.extend(a[i:]) # phần đuôi còn lại, đã sắp xếp sẵn
out.extend(b[j:])
return out
assert merge_sorted([2, 5, 9, 14], [1, 3, 8, 20, 25]) == \
[1, 2, 3, 5, 8, 9, 14, 20, 25]
```
4
Bất biến giữ trong suốt vòng lặp: mọi phần tử đã ghi ra `out` đều ≤ mọi phần tử còn lại trong a[i:] và b[j:] — vì `out` chỉ nhận phần tử nhỏ nhất trong hai phần tử "đầu" đang xét, mà hai phần tử đó lại nhỏ nhất trong phần dãy còn lại của chính nó. Do đó dãy `out` luôn không giảm. Mỗi bước có ít nhất một chỉ số tiến, tổng số bước tối đa là len(a) + len(b), nên độ phức tạp O(n + m), không phải O((n+m) log(n+m)) như sort lại từ đầu.
Bẫy thường gặp
Mở rộng dành cho HSG: đề đôi khi cho "trộn k dãy đã sắp xếp" thay vì 2 dãy — hai con trỏ cùng chiều chỉ trực tiếp xử lý k = 2. Với k lớn hơn, kỹ thuật đúng là trộn từng cặp một theo kiểu cây (như merge sort đệ quy) hoặc dùng heap k phần tử — nội dung đó thuộc Khóa 5 (chia để trị) và Khóa 3 (cấu trúc dữ liệu), không mở rộng ở đây.
Mở rộng dành cho HSG: ba con trỏ cho tổng ba số bằng 0
Bài toán "tìm ba phần tử có tổng bằng 0" (3-sum) không nằm trong yêu cầu chuẩn của lớp 11, nhưng là biến thể HSG rất hay gặp của hai con trỏ: cố định một chỉ số i, phần còn lại của mảng trở thành đúng bài toán "tìm cặp có tổng bằng −a[i]" ở Ví dụ 1. Lặp i từ trái sang phải, mỗi lần chạy hai con trỏ trên phần còn lại — tổng độ phức tạp O(n) cho vòng ngoài nhân O(n) cho hai con trỏ bên trong, tức O(n²), thay vì thử mọi bộ ba trực tiếp tốn O(n³).
Ví dụ
Ví dụ 3 — Tổng ba số bằng 0 bằng cố định một chỉ số và hai con trỏ
1
Cho mảng a = [-4, -1, -1, 0, 1, 2]. Tìm tất cả bộ ba chỉ số phân biệt (không nhất thiết liền kề) có tổng giá trị bằng 0, không lặp lại cùng một bộ giá trị.
2
Mảng đã cho sẵn ở dạng sắp xếp không giảm: [-4, -1, -1, 0, 1, 2]. Nếu đề chưa sắp xếp, bước sắp xếp tốn O(n log n), không làm đổi độ phức tạp tổng thể O(n²).
3
Cần tìm cặp trong đoạn còn lại [-1, -1, 0, 1, 2] có tổng bằng −a[i] = 4. Hai con trỏ: lo=1(−1), hi=5(2): tổng −1+2=1<4, tăng lo. lo=2(−1),hi=5(2): tổng 1<4, tăng lo. lo=3(0),hi=5(2): tổng 2<4, tăng lo. lo=4(1),hi=5(2): tổng 3<4, tăng lo, lo=hi dừng. Không có cặp nào — với i=0 không có bộ ba nào.
4
Cần tổng bằng −a[i] = 1 trong đoạn [-1, 0, 1, 2] (chỉ số 2 đến 5). lo=2(−1),hi=5(2): tổng 1=1 — tìm thấy bộ ba (−1, −1, 2). Dịch lo=3, hi=4: lo=3(0),hi=4(1): tổng 1=1 — tìm thấy bộ ba (−1, 0, 1). Dịch tiếp lo=4=hi, dừng.
5
i=2 có a[2]=−1=a[1] — trùng giá trị với i vừa xét, bỏ qua ngay để tránh đếm lại cùng một bộ ba (−1,−1,2) lần thứ hai. i=3,4 không còn đủ hai phần tử phía sau để tạo cặp có tổng dương cần thiết (kiểm tra nhanh: không cho kết quả mới).
6
```python
def three_sum_zero(a):
a = sorted(a)
n = len(a)
res = set()
for i in range(n):
if i > 0 and a[i] == a[i - 1]:
continue # bỏ chỉ số i trùng giá trị, tránh đếm lặp
lo, hi = i + 1, n - 1
target = -a[i]
while lo < hi:
s = a[lo] + a[hi]
if s == target:
res.add((a[i], a[lo], a[hi]))
lo += 1; hi -= 1
elif s < target:
lo += 1
else:
hi -= 1
return res
assert three_sum_zero([-4, -1, -1, 0, 1, 2]) == \
{(-1, -1, 2), (-1, 0, 1)}
```
7
Vậy có đúng hai bộ ba: (−1, −1, 2) và (−1, 0, 1) — cả hai đều tổng bằng 0. Độ phức tạp O(n²), so với O(n³) nếu thử mọi bộ ba trực tiếp — với n = 5000 thì n² ≈ 2,5·10⁷ (chạy được trong một giây), còn n³ ≈ 1,25·10¹¹ (chắc chắn timeout).
Bẫy thường gặp
Bẫy thường gặp: quên bỏ qua chỉ số i trùng giá trị (hoặc quên bỏ qua lo/hi trùng giá trị sau khi tìm được một bộ ba) sẽ khiến cùng một bộ ba bị đếm nhiều lần — đúng về giá trị nhưng sai về số lượng nếu đề hỏi "đếm bao nhiêu bộ ba phân biệt". Bẫy thứ hai: áp dụng trực tiếp hai con trỏ lên mảng **chưa sắp xếp** — kỹ thuật này bắt buộc mảng đơn điệu, sắp xếp trước là bước không thể bỏ qua dù tốn thêm O(n log n).
Tóm tắt
Hai con trỏ thay một vòng lặp lồng O(n²) bằng hai chỉ số cùng tiến một chiều, tổng cộng chạy O(n). Ngược chiều dùng cho "tìm một cặp" trên dãy đơn điệu; cùng chiều dùng cho "trộn hai dãy đã sắp xếp". Mở rộng lên ba con trỏ (cố định một chỉ số) hạ 3-sum từ O(n³) xuống O(n²). Điều kiện bắt buộc trong mọi trường hợp: dãy phải đơn điệu hoặc đã sắp xếp — thiếu điều kiện này, lập luận đúng đắn sụp đổ.
Bài tiếp theo giữ nguyên hai con trỏ nhưng đổi câu hỏi: thay vì tìm MỘT cặp tốt nhất, ta cần tìm MỘT ĐOẠN liên tục tốt nhất thỏa điều kiện — đó là lúc hai con trỏ tiến hóa thành cửa sổ trượt.
Lớp 10 em đã quen tìm kiếm nhị phân và duyệt mảng một lượt O(n). Bài này đi xa hơn: khi mảng đã sắp xếp hoặc có tính đơn điệu, hai chỉ số chạy cùng lúc — mỗi chỉ số chỉ tăng, không bao giờ lùi — có thể thay thế cả một vòng lặp lồng O(n²). Học xong, em tự thiết kế và chứng minh được một lời giải hai con trỏ, không chỉ bắt chước khuôn mẫu.
Đề chuẩn thường dừng ở mức: cho mảng đã sắp xếp, tìm xem có tồn tại hai phần tử tổng bằng S hay không — nested loop hai lớp, O(n²), n nhỏ thì chạy kịp. Đề HSG đẩy xa hơn theo hai hướng: (1) ràng buộc n lớn (10⁵ trở lên) khiến O(n²) chắc chắn timeout, buộc phải hạ xuống O(n); (2) đề còn yêu cầu đếm số cặp thỏa điều kiện, hoặc mở rộng sang ba phần tử — không còn là bài tra cứu tồn tại/không tồn tại đơn giản.
Cho mảng a gồm n số nguyên, đã sắp xếp không giảm, và một số S. Tìm hai chỉ số i < j sao cho a[i] + a[j] = S. Nếu duyệt mọi cặp, độ phức tạp là O(n²) — với n = 10⁵ thì khoảng 10¹⁰ phép so sánh, vượt xa giới hạn một giây chấm bài. Mảng đã sắp xếp — thông tin đó phải được tận dụng, không thể bỏ phí.
Đặt lo = 0 ở đầu mảng, hi = n − 1 ở cuối mảng. Xét tổng a[lo] + a[hi]. Nếu tổng đúng bằng S, xong. Nếu tổng nhỏ hơn S, phải tăng tổng lên — mà a[hi] đã là phần tử lớn nhất còn lại trong đoạn đang xét, nên cách duy nhất để tăng tổng là dịch lo sang phải, lấy một a[lo] lớn hơn. Ngược lại nếu tổng lớn hơn S, dịch hi sang trái. Mỗi bước, đúng một trong hai con trỏ tiến vào trong; vòng lặp dừng khi lo ≥ hi. Tổng số bước tối đa là n, nên độ phức tạp là O(n).
Đây là chỗ học sinh hay tin mà không chứng minh. Giả sử tại một bước a[lo] + a[hi] < S và ta quyết định tăng lo. Cần chỉ ra: không cặp nào chứa hi hiện tại và một chỉ số nhỏ hơn lo bị bỏ lỡ. Thật vậy, với mọi lo' < lo, vì mảng không giảm nên a[lo'] ≤ a[lo], suy ra a[lo'] + a[hi] ≤ a[lo] + a[hi] < S — cặp (lo', hi) chắc chắn không đạt tổng S, nên bỏ qua toàn bộ các lo' đó là an toàn. Lập luận đối xứng áp dụng khi tổng lớn hơn S và ta giảm hi. Đây chính là phần "chứng minh đúng đắn" mà đề viết HSG luôn đòi hỏi, không chỉ code chạy ra kết quả đúng trên vài test.
Với mảng rỗng, lo=0, hi=-1, vòng lặp không chạy lần nào, hàm trả về None ngay — đúng, không có cặp nào. Với mảng chỉ một phần tử, lo=hi=0, điều kiện lo<hi sai ngay, cũng trả về None — đúng, một phần tử không tạo được cặp. Vậy cặp duy nhất cho ví dụ trên là (5, 22), tại chỉ số (2, 7), độ phức tạp O(n).
Hai con trỏ ngược chiều xử lý bài toán "tìm một cặp". Khi bài toán là gộp hai dãy đã sắp xếp thành một dãy sắp xếp, hai con trỏ chạy cùng chiều (đều chỉ tiến, không bao giờ đổi hướng) mới là kỹ thuật đúng — mỗi bước so sánh phần tử đang trỏ tới của hai dãy, lấy phần tử nhỏ hơn, rồi tiến con trỏ tương ứng. Đây chính là bước "trộn" (merge) sẽ dùng lại nguyên vẹn trong thuật toán sắp xếp trộn ở Khóa 5 (chia để trị).
def merge_sorted(a, b):
i = j = 0
out = []
while i < len(a) and j < len(b):
if a[i] <= b[j]:
out.append(a[i]); i += 1
else:
out.append(b[j]); j += 1
out.extend(a[i:]) # phần đuôi còn lại, đã sắp xếp sẵn
out.extend(b[j:])
return out
assert merge_sorted([2, 5, 9, 14], [1, 3, 8, 20, 25]) == \
[1, 2, 3, 5, 8, 9, 14, 20, 25]
Bất biến giữ trong suốt vòng lặp: mọi phần tử đã ghi ra out đều ≤ mọi phần tử còn lại trong a[i:] và b[j:] — vì out chỉ nhận phần tử nhỏ nhất trong hai phần tử "đầu" đang xét, mà hai phần tử đó lại nhỏ nhất trong phần dãy còn lại của chính nó. Do đó dãy out luôn không giảm. Mỗi bước có ít nhất một chỉ số tiến, tổng số bước tối đa là len(a) + len(b), nên độ phức tạp O(n + m), không phải O((n+m) log(n+m)) như sort lại từ đầu.
Bài toán "tìm ba phần tử có tổng bằng 0" (3-sum) không nằm trong yêu cầu chuẩn của lớp 11, nhưng là biến thể HSG rất hay gặp của hai con trỏ: cố định một chỉ số i, phần còn lại của mảng trở thành đúng bài toán "tìm cặp có tổng bằng −a[i]" ở Ví dụ 1. Lặp i từ trái sang phải, mỗi lần chạy hai con trỏ trên phần còn lại — tổng độ phức tạp O(n) cho vòng ngoài nhân O(n) cho hai con trỏ bên trong, tức O(n²), thay vì thử mọi bộ ba trực tiếp tốn O(n³).
def three_sum_zero(a):
a = sorted(a)
n = len(a)
res = set()
for i in range(n):
if i > 0 and a[i] == a[i - 1]:
continue # bỏ chỉ số i trùng giá trị, tránh đếm lặp
lo, hi = i + 1, n - 1
target = -a[i]
while lo < hi:
s = a[lo] + a[hi]
if s == target:
res.add((a[i], a[lo], a[hi]))
lo += 1; hi -= 1
elif s < target:
lo += 1
else:
hi -= 1
return res
assert three_sum_zero([-4, -1, -1, 0, 1, 2]) == \
{(-1, -1, 2), (-1, 0, 1)}
Bẫy thường gặp: quên bỏ qua chỉ số i trùng giá trị (hoặc quên bỏ qua lo/hi trùng giá trị sau khi tìm được một bộ ba) sẽ khiến cùng một bộ ba bị đếm nhiều lần — đúng về giá trị nhưng sai về số lượng nếu đề hỏi "đếm bao nhiêu bộ ba phân biệt". Bẫy thứ hai: áp dụng trực tiếp hai con trỏ lên mảng chưa sắp xếp — kỹ thuật này bắt buộc mảng đơn điệu, sắp xếp trước là bước không thể bỏ qua dù tốn thêm O(n log n).
Hai con trỏ thay một vòng lặp lồng O(n²) bằng hai chỉ số cùng tiến một chiều, tổng cộng chạy O(n). Ngược chiều dùng cho "tìm một cặp" trên dãy đơn điệu; cùng chiều dùng cho "trộn hai dãy đã sắp xếp". Mở rộng lên ba con trỏ (cố định một chỉ số) hạ 3-sum từ O(n³) xuống O(n²). Điều kiện bắt buộc trong mọi trường hợp: dãy phải đơn điệu hoặc đã sắp xếp — thiếu điều kiện này, lập luận đúng đắn sụp đổ.