Level 1 · Cơ bản

Two pointers

Kỹ thuật hai con trỏ trên mảng/chuỗi đã sắp xếp.

Trung bình Visualizer tương tác8 bài luyện tập

Ý tưởng chính

Two pointers dùng hai chỉ số di chuyển trên mảng để giảm độ phức tạp từ O(n²) xuống O(n) trong nhiều bài toán về cặp phần tử, subarray.

Hình dung

Hai người đứng ở hai đầu một dãy người đã xếp theo chiều cao, cần tìm hai người có tổng chiều cao đúng bằng một số. Tổng quá lớn thì người bên phải bước vào, quá nhỏ thì người bên trái bước vào — không ai phải quay lại.

Cách hoạt động

1
Đặt con trỏ left ở đầu mảng và right ở cuối mảng (mảng đã sắp xếp).
2
Tính tổng arr[left] + arr[right] và so với mục tiêu.
3
Tổng nhỏ hơn: tăng left để tổng lớn lên. Tổng lớn hơn: giảm right để tổng nhỏ lại.
4
Dừng khi tìm thấy hoặc hai con trỏ gặp nhau. Biến thể cửa sổ trượt: cả hai con trỏ cùng đi từ trái sang phải.

Độ phức tạp

O(n): mỗi con trỏ chỉ đi một chiều, tổng cộng tối đa n bước — thay cho O(n²) khi thử mọi cặp.

Khi nào dùng

Tìm cặp/bộ phần tử trên mảng đã sắp xếp, hoặc tìm đoạn con liên tiếp dài nhất/ngắn nhất thoả điều kiện (cửa sổ trượt).

Lỗi hay gặp

Quên sắp xếp mảng trước khi dùng kiểu hai đầu.
Dùng cửa sổ trượt khi điều kiện không đơn điệu (ví dụ mảng có số âm với bài tổng ≤ K) — kỹ thuật không còn đúng.

Liên hệ thực tế

Ứng dụng thực tế

Kỹ thuật này xuất hiện ở đâu ngoài đời — để bạn có sẵn một hình ảnh cụ thể khi học.

Giới hạn tốc độ request (rate limiting)
Giữ cửa sổ trượt các request trong 60 giây gần nhất: con trỏ phải thêm request mới, con trỏ trái bỏ request đã quá hạn.
Trộn và so sánh hai danh sách đã sắp xếp
Lệnh comm trên Unix hay việc đối chiếu hai danh bạ tìm liên hệ chung đều đi song song hai con trỏ trên hai danh sách.
Chọn cặp sản phẩm vừa ngân sách
Với danh sách giá đã sắp xếp, tìm hai món có tổng giá đúng bằng (hoặc gần nhất) số tiền voucher trong O(n).
Tìm đoạn dài nhất thoả điều kiện
Ví dụ khoảng thời gian dài nhất mà tổng chi tiêu không vượt hạn mức, hay chuỗi con dài nhất không lặp ký tự.

Xem thuật toán chạy

Minh hoạ từng bước

Chạy tự động hoặc đi từng bước; theo dõi hình minh hoạ, lời giải thích, giá trị biến và dòng code tương ứng cùng lúc.

Bấm vào khung minh hoạ, rồi:Space chạy / dừng←→ từng bướcHomeEnd đầu / cuối

Tự làm

Luyện tập trên Codeforces

Sắp xếp từ dễ đến khó theo rating, mỗi bài kèm tóm tắt đề. Bí thì mở gợi ý — có 3 mức, từ hướng suy nghĩ tới gần lời giải.

Rating 1200
Three Parts of the Array(mở Codeforces trong tab mới)
Cho mảng số nguyên dương. Chia mảng thành 3 đoạn liên tiếp (có thể rỗng) sao cho tổng đoạn đầu bằng tổng đoạn cuối. Tìm giá trị lớn nhất của tổng đó.
Test mẫu & giải thích
Input
5 1 3 1 1 4
Output
5
Mảng [1,3,1,1,4]: dùng hai con trỏ từ hai đầu, đoạn đầu lấy {1,3} tổng 4 trong khi đoạn cuối lấy {4} tổng 4, hai tổng đã bằng nhau nhưng còn mở rộng được. Mở đoạn đầu thêm phần tử thứ 3 (giá trị 1) được tổng 5, đồng thời mở đoạn cuối thêm phần tử thứ 4 (giá trị 1) cũng được tổng 5; hai đoạn {1,3,1} và {1,4} không chồng lấn (dùng hết 5 phần tử, đoạn giữa rỗng) và có tổng bằng nhau là 5. Đây là giá trị lớn nhất có thể vì mở rộng thêm nữa sẽ khiến hai đoạn chồng lên nhau, khớp kết quả 5.
Rating 1200
Lecture Sleep(mở Codeforces trong tab mới)
Bài giảng dài n phút, phút i giảng a_i định lý; t_i = 1 nếu Mishka thức (ghi lại được), 0 nếu ngủ. Bạn được dùng kỹ thuật một lần để giữ anh ấy thức trong k phút liên tiếp. Tìm tổng số định lý ghi được lớn nhất.
Test mẫu & giải thích
Input
6 3 1 3 5 2 5 4 1 1 0 1 0 0
Output
16
Số định lý ghi được sẵn (không dùng kỹ thuật) là tổng các phút có t_i=1: phút1(1)+phút2(3)+phút4(2)=6. Kỹ thuật áp dụng cho k=3 phút liên tiếp sẽ ghi được toàn bộ a_i của các phút đó bất kể trạng thái ngủ/thức, nên chỉ có lợi thêm ở các phút đang ngủ (t_i=0): phút3(5) và phút5,6(5,4). Cửa sổ 3 phút [3,4,5] cho thêm 5(phút3,đang ngủ)+0(phút4,đã thức)+5(phút5,đang ngủ)=10, lớn hơn mọi cửa sổ khác (ví dụ [4,5,6] chỉ thêm 0+5+4=9). Tổng cuối = 6 (đã ghi sẵn) + 10 (tăng thêm) = 16, khớp kết quả.
Rating 1300
Queries about less or equal elements(mở Codeforces trong tab mới)
Cho hai mảng a (n phần tử) và b (m phần tử). Với mỗi b_j, đếm số phần tử của a nhỏ hơn hoặc bằng b_j.
Test mẫu & giải thích
Input
5 4 1 3 5 7 9 6 4 2 8
Output
3 2 1 4
Test 1
Với b_1=6: các phần tử a≤6 là {1,3,5}, đếm được 3.
Test 2
Với b_2=4: các phần tử a≤4 là {1,3}, đếm được 2.
Test 3
Tương tự b_3=2 chỉ có {1} thoả nên đếm được 1.
Test 4
b_4=8 có {1,3,5,7} thoả nên đếm được 4; khớp dãy kết quả '3 2 1 4'.
Rating 1400
Swap Adjacent Elements(mở Codeforces trong tab mới)
Cho hoán vị a của 1..n và chuỗi nhị phân độ dài n − 1: s_i = 1 nghĩa là được đổi chỗ a_i với a_{i+1} bao nhiêu lần tuỳ ý. Hỏi có sắp xếp tăng dần được mảng không.
Test mẫu & giải thích
Input
6 1 2 5 3 4 6 01110
Output
YES
Chuỗi s='01110' cho phép đổi chỗ tự do giữa các cặp vị trí (2,3),(3,4),(4,5) (các bit '1' ở vị trí 2,3,4), ghép các vị trí 2-3-4-5 thành một khối liên thông có thể hoán vị nội bộ tuỳ ý, còn vị trí 1 và 6 bị cô lập (bit '0' ở đầu và cuối). Vị trí 1 đang giữ giá trị 1 và vị trí 6 đang giữ giá trị 6, đúng vị trí cần có khi mảng đã sắp xếp. Bốn vị trí giữa hiện chứa {2,5,3,4}, đúng bằng tập giá trị {2,3,4,5} cần có ở đó, nên nhờ khối liên thông có thể sắp xếp lại thành 2,3,4,5, toàn mảng thành dãy tăng dần, do đó kết quả là YES.
Rating 1500
Sorting the Coins(mở Codeforces trong tab mới)
Có n đồng xu xếp hàng, ban đầu đều 'ngoài lưu thông'. Thuật toán của Dima lặp lượt quét: đồng trong lưu thông mà đồng bên phải ngoài lưu thông thì đổi chỗ; độ khó là số lượt quét tới khi không đổi gì. Sasha lần lượt thay n đồng ở các vị trí p_i thành 'trong lưu thông' — in độ khó trước và sau mỗi lần thay.
Test mẫu & giải thích
Input
4 1 3 4 2
Output
1 2 3 2 1
Test 1
Trạng thái ban đầu chưa đồng nào lưu thông [0,0,0,0]: quét một lượt không có cặp (1,0) liền kề nào để đổi chỗ, thuật toán dừng ngay sau 1 lượt, độ khó = 1.
Test 2
Sau khi đưa vị trí 1 vào lưu thông, mảng là [1,0,0,0]: lượt 1 đẩy số 1 trượt dần qua các số 0 liền kề thành [0,0,0,1], lượt 2 không còn cặp nào để đổi nên dừng, độ khó = 2.
Test 3
Sau khi thêm vị trí 3, mảng là [1,0,1,0]: lượt 1 thành [0,1,0,1], lượt 2 thành [0,0,1,1], lượt 3 không đổi gì nữa nên dừng, độ khó = 3.
Test 4
Tiếp tục thêm vị trí 4 ([1,0,1,1]) chỉ cần 2 lượt.
Test 5
Thêm vị trí 2 (toàn bộ thành [1,1,1,1], không còn cặp 1 kề 0) chỉ cần 1 lượt để nhận ra đã dừng, cho ra dãy độ khó đầy đủ '1 2 3 2 1'.
Rating 1500
Kefa and Company(mở Codeforces trong tab mới)
Kefa có n người bạn, người i có m_i tiền và hệ số tình bạn s_i. Không ai được thấy mình nghèo: chênh lệch tiền giữa hai người trong nhóm phải nhỏ hơn d. Chọn nhóm có tổng hệ số tình bạn lớn nhất.
Test mẫu & giải thích
Input
4 5 75 5 0 100 150 20 75 1
Output
100
Điều kiện là chênh lệch tiền giữa hai người bất kỳ trong nhóm phải nhỏ hơn d=5. Người thứ hai có m=0 bị cô lập hẳn về tiền (người gần nhất có m=75, chênh lệch 75≥5) nên không thể ghép nhóm cùng ai, chỉ có thể đứng một mình, cho tổng hệ số tình bạn 100. Các nhóm gồm những người có m=75 (hệ số 5 và 1) may lắm đạt tổng 6, thấp hơn nhiều so với 100, nên phương án tối ưu là chọn riêng người có m=0, khớp kết quả 100.
Rating 1600
Convenient For Everybody(mở Codeforces trong tab mới)
Có n múi giờ liên tiếp, múi i có a_i người; giờ ở múi i+1 hơn múi i một tiếng. Cuộc thi kéo dài 1 giờ, một người tham gia nếu cuộc thi bắt đầu không sớm hơn s:00 và kết thúc không muộn hơn f:00 giờ địa phương. Chọn giờ bắt đầu (theo múi 1) để có nhiều người tham gia nhất.
Test mẫu & giải thích
Input
3 1 2 3 1 3
Output
3
Ở đây n=3 vừa là số múi giờ vừa là số giờ trong một ngày (giờ chạy vòng từ 1 đến 3, khi múi 1 là 1 giờ thì múi i là i giờ). Cửa sổ giờ địa phương hợp lệ để tham gia là [s, f-1] = [1,2] vì bắt đầu đúng lúc f giờ thì người đó không được tính. Nếu chọn giờ bắt đầu ở múi 1 là 3 giờ thì múi 2 sẽ là 1 giờ (hợp lệ, 2 người) và múi 3 sẽ là 2 giờ (hợp lệ, 3 người), chỉ nhóm 1 người ở múi 1 (lúc đó là giờ 3, không hợp lệ) bị bỏ lỡ; đây là phương án tốt nhất vì chỉ loại bỏ nhóm nhỏ nhất trong ba nhóm, nên đáp số là giờ bắt đầu 3.
Rating 1600
Three-level Laser(mở Codeforces trong tab mới)
Có n mức năng lượng E_1 < E_2 < … < E_n. Chọn ba trạng thái i < j < k với E_k − E_i ≤ U; hiệu suất là (E_k − E_j) / (E_k − E_i). Tìm hiệu suất lớn nhất, hoặc −1 nếu không chọn được.
Test mẫu & giải thích
Input
4 4 1 3 5 7
Output
0.5
Với n=4, U=4, E=[1,3,5,7], chỉ có 4 bộ ba (i,j,k) khả dĩ. Bộ (1,2,3): E_k-E_i=5-1=4≤U nên hợp lệ, hiệu suất (E_3-E_2)/(E_3-E_1)=(5-3)/(5-1)=0.5. Bộ (2,3,4): E_k-E_i=7-3=4≤U cũng hợp lệ, hiệu suất (7-5)/(7-3)=0.5. Hai bộ còn lại (1,2,4) và (1,3,4) đều có E_k-E_i=6>U=4 nên bị loại. Vì hai bộ hợp lệ duy nhất đều cho cùng hiệu suất 0.5, đó chính là giá trị lớn nhất, khớp sampleOutput.