Phá đảo 150 DSA Tập 1 - Arrays & Hashing: Contains Duplicate

Bắt đầu hành trình 150 bài DSA bằng một bài toán tưởng như “mẫu giáo” nhưng lại chứa đựng một kiến thức cực kỳ quyền lực: Hashing. “Contains Duplicate” chỉ đơn giản yêu cầu bạn tìm xem có con số nào lặp lại trong một mảng hay không. Nếu theo tư duy tự nhiên nhất, chúng ta hay giải bằng Brute Force là đem từng số đi so sánh với tất cả các số còn lại, nhưng cách này thì thực sự quá chậm. Nhạy bén hơn một chút, chúng ta có thể sắp xếp (Sorting) mảng lại để các số giống nhau tự động chạy đến đứng cạnh nhau, giúp việc tìm kiếm nhanh hơn đáng kể. Tuy nhiên, “trùm cuối” cho bài toán này phải là HashSet. Nôm na là chúng ta chỉ cần dùng thêm một “cuốn sổ tay” bộ nhớ, cứ đi qua số nào thì ghi số đó vào sổ. Điểm kỳ diệu của HashSet là tốc độ kiểm tra xem một số đã có mặt trong sổ chưa gần như là tức thì. Bằng cách đánh đổi một chút không gian lưu trữ để nhận lại tốc độ duyệt O(n) thần tốc, đây chính là “vũ khí” cốt lõi mà bạn sẽ còn đem đi dùng lại rất nhiều lần trong các cuộc phỏng vấn thuật toán. Vuốt sang bên để xem từng cách giải này được mình mô phỏng chi tiết bằng hình ảnh cực cute nhé!