Contains Duplicate

Bài toán

Cho một mảng các số nguyên nums. Trả về true nếu có bất kỳ giá trị nào xuất hiện ít nhất 2 lần trong mảng, và trả về false nếu mọi phần tử đều là duy nhất.

Ví dụ 1:

Input: nums = [1,2,3,1]
Output: true

Ví dụ 2:

Input: nums = [1,2,3,4]
Output: false

Phân Tích & Tiếp Cận

Cách 1: Brute Force (Vét cạn)

Duyệt qua từng phần tử, và với mỗi phần tử đó, duyệt lại các phần tử phía sau để xem có trùng không.

function containsDuplicate(nums: number[]): boolean {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] === nums[j]) {
                return true;
            }
        }
    }
    return false;
}

• Time Complexity: $O(n^2)$ - Quá chậm nếu $n$ lớn (vd: $10^5$).
• Space Complexity: $O(1)$ - Không dùng thêm bộ nhớ.

Cách 2: Sorting (Sắp xếp)

Nếu mảng được sắp xếp, các phần tử trùng nhau sẽ nằm cạnh nhau.

function containsDuplicate(nums: number[]): boolean {
    nums.sort((a, b) => a - b); // O(n log n)
    for (let i = 0; i < nums.length - 1; i++) {
        if (nums[i] === nums[i+1]) {
            return true;
        }
    }
    return false;
}

• Time Complexity: $O(n \log n)$ - Do chi phí sắp xếp.
• Space Complexity: $O(1)$ (hoặc $O(\log n)$ tùy thuật toán sort).

Cách 3: Hash Set (Tối ưu)

Sử dụng Set trong JavaScript. Set là cấu trúc dữ liệu chỉ chứa các giá trị duy nhất và cho phép kiểm tra tồn tại (lookup) với độ phức tạp trung bình là $O(1)$.

function containsDuplicate(nums: number[]): boolean {
    const seen = new Set<number>();
    
    for (const num of nums) {
        if (seen.has(num)) { // Kiểm tra O(1)
            return true;
        }
        seen.add(num); // Thêm vào O(1)
    }
    
    return false;
}

Thủ thuật One-Liner (JavaScript): So sánh độ dài của mảng gốc và Set được tạo từ mảng đó.

function containsDuplicate(nums: number[]): boolean {
    return new Set(nums).size !== nums.length;
}

• Time Complexity: $O(n)$ - Duyệt mảng 1 lần.
• Space Complexity: $O(n)$ - Trường hợp xấu nhất phải lưu toàn bộ mảng vào Set.

Kinh Nghiệm Thực Tế (Key Takeaways)

1. Đánh đổi (Trade-off): Ở đây ta chấp nhận tốn RAM (Space $O(n)$) để đổi lấy Tốc độ (Time $O(n)$). Trong hầu hết các ứng dụng Web/App hiện đại, RAM rẻ hơn CPU time, nên ưu tiên tốc độ phản hồi.
2. Sức mạnh của Set/Map: Bất cứ khi nào cần kiểm tra "đã xuất hiện chưa" hoặc "tìm kiếm", hãy nghĩ ngay đến Hash Table (Set hoặc Object/Map).
3. Dữ liệu lớn: Nếu nums có 1 tỷ phần tử, cách dùng Set có thể gây tràn bộ nhớ (Out of Memory). Khi đó Cách 2 (Sort hoặc External Sort) lại trở thành lựa chọn khả dĩ hơn.