Contains Duplicate: người anh em thoái hoá của Two Sum

Đây là Two Sum đã bỏ phép tính. Thay vì kiểm tra xem một giá trị đã thấy trước có hoàn thành một cặp không, bạn chỉ kiểm tra xem chính giá trị đó đã xuất hiện chưa. Cùng cấu trúc dữ liệu. Ít một thao tác.

Bài toán: cho nums, trả về true nếu có giá trị nào xuất hiện ít nhất hai lần. Hai constraint làm phần lớn công việc thiết kế trước khi bạn viết một dòng code.

1 <= nums.length <= 10^5 — ở kích thước này, bất cứ thứ gì O(n^2) cần khoảng 5 tỷ phép tính. Điều đó loại bỏ brute force khỏi cân nhắc production. -10^9 <= nums[i] <= 10^9 — các số nguyên trải rộng 2 × 10^9 giá trị. Một mảng boolean 2 tỷ phần tử cho direct-index là không khả thi. Khoảng giá trị đó buộc bạn đến hash-based structure hoặc comparison sort.

Vậy trước khi nghĩ đến thuật toán: các constraint đã thu hẹp lựa chọn xuống còn hash set (O(n)) hoặc sort (O(n log n)). Brute force vẫn đáng hiểu vì nó cho thấy chính xác cái gì mà hash set loại bỏ.

Brute force: so sánh từng cặp

Với mỗi phần tử tại chỉ số i, quét qua toàn bộ phần tử tại chỉ số j > i. Nếu có hai phần tử trùng nhau, return true.

Trace qua nums = [1, 2, 3, 1]:

Vòng lặp trong ở i=0 tìm thấy đáp án tại j=3. Trong trường hợp xấu nhất (không có duplicate nào), bạn phải duyệt hết toàn bộ n(n-1)/2 cặp.

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        n = len(nums)
        for i in range(n - 1):
            for j in range(i + 1, n):
                if nums[i] == nums[j]:
                    return True
        return False

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        int n = nums.Length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j])
                    return true;
            }
        }
        return false;
    }
}

O(n^2) thời gian, O(1) space. Đúng. Quá chậm ở quy mô thực tế — LeetCode timeout ở n = 10^5. Quan sát thú vị hơn: vòng lặp lồng nhau đang trả lời câu hỏi "có phần tử nào trước đó trùng với cái này không?" bằng cách kiểm tra tất cả phần tử trước đó. Hash set trả lời câu hỏi tương tự trong O(1) vì nó đã đánh chỉ mục chúng rồi.

Hash set approach: O(n)

Giữ một set của mọi thứ đã đi qua. Với mỗi số, kiểm tra membership trước khi chèn vào. Set làm trong O(1) những gì vòng lặp trong làm trong O(n).

Đây là state trace, từng bước, trên nums = [1, 2, 3, 1]:

Ở bước 4 ta gặp early exit. Set đã đánh chỉ mục 1 ở bước 1, nên việc tra cứu ở bước 4 là O(1).

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False

O(n) thời gian, O(n) bộ nhớ. Chi phí space là trade-off: trong trường hợp xấu nhất (không có duplicate) set phình lên đến n phần tử. Đổi lại, early-exit trên input có duplicate gần đầu mảng thực sự nhanh — mảng 10^5 phần tử mà nums[0] == nums[1] kết thúc sau 2 lần lặp.

Trong C#, HashSet<T>.Add trả về false khi phần tử đã có trong set. Điều đó gộp việc kiểm tra và chèn vào thành một lần gọi:

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        var seen = new HashSet<int>();
        foreach (int num in nums) {
            if (!seen.Add(num))   // Add trả false nếu num đã có trong set
                return true;
        }
        return false;
    }
}

Tôi dùng idiom này trong mọi bài seen-set bằng C#. Ít hơn một lần gọi method mỗi vòng lặp, và intent đọc rõ ràng khi bạn biết Add trả về gì.

One-liner Python và lý do tôi không dùng trong phỏng vấn

Python cho phép so sánh kích thước set với độ dài mảng:

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        return len(set(nums)) != len(nums)

Đúng. Nhưng có vấn đề: nó luôn xử lý toàn bộ mảng. Không có early exit. Trên mảng 10^5 phần tử mà nums[0] == nums[1], vòng lặp tường minh kết thúc sau 2 lần lặp; set(nums) vẫn xử lý hết 10^5 số trước khi bạn kiểm tra độ dài. Trong phỏng vấn tôi đề cập điểm này, rồi viết vòng lặp tường minh để cho thấy tôi đã suy nghĩ về nó.

Sorting: lựa chọn tiết kiệm bộ nhớ

Sort mảng. Các duplicate nào cũng phải nằm cạnh nhau sau khi sort. Sau đó một lần quét tuyến tính là đủ để phát hiện chúng.

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        nums.sort()
        for i in range(len(nums) - 1):
            if nums[i] == nums[i + 1]:
                return True
        return False

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        Array.Sort(nums);
        for (int i = 0; i < nums.Length - 1; i++) {
            if (nums[i] == nums[i + 1])
                return true;
        }
        return false;
    }
}

O(n log n) thời gian, O(1) bộ nhớ thêm — giả sử sort in-place. Timsort của Python và Array.Sort của C# đều in-place. Lợi thế về space là thật.

Chi phí mà đề bài không đề cập: nó biến đổi mảng input. Nếu bên gọi giữ tham chiếu đến nums và định dùng lại sau khi method trả về, bạn vừa âm thầm sắp xếp lại nó. LeetCode không quan tâm điều đó. Trong production service đôi khi lại quan tâm. Đây là loại bug thực sự — tôi đã thấy nó trong code review nhiều lần hơn tôi muốn thừa nhận — nên tôi coi input mutation là trade-off không tầm thường, không phải chú thích học thuật.

Khi hệ thống yêu cầu không có thêm allocation (code nhúng, pipeline bị giới hạn bộ nhớ), sorting là lựa chọn đúng. Còn lại tôi mặc định dùng hash set và chấp nhận O(n) space.

So sánh ba cách tiếp cận

Cái tôi sẽ dùng thực tế: hash set, hầu như luôn luôn. Sorting chỉ xuất hiện khi ai đó nói rõ ràng "giảm thiểu allocation" hoặc môi trường không thể chịu được heap growth. Brute force không bao giờ là đáp án đúng ở đây — nó chỉ tồn tại để cho thấy bạn đang tối ưu cái gì.

Edge case

Mảng một phần tử [5]: không có cặp nào để so sánh. Vòng lặp brute force không bao giờ thực thi phần thân vì range(n - 1) rỗng khi n = 1. Hash set thêm 5, vòng lặp kết thúc, trả về false. Cả hai đúng mà không cần xử lý đặc biệt.

Hai phần tử bằng nhau [3, 3]: trường hợp duplicate tối thiểu. Brute force so sánh một cặp và tìm thấy. Hash set thêm 3, rồi ở lần 3 thứ hai gặp ngay if num in seen. Đáng test riêng vì lỗi off-by-one trong giới hạn vòng lặp (range(n - 1) vs range(n)) có thể âm thầm bỏ qua trường hợp này — vòng lặp trong j cần đến được chỉ số 1.

Toàn bộ giống nhau [7, 7, 7, 7]: hash set kết thúc ở bước 2 (num=7 tìm thấy trong seen). Sorting tìm duplicate ở i=0 ngay lần kiểm tra đầu tiên. Cả hai early-exit đúng.

Giá trị âm [-10^9, -10^9]: hash set đánh chỉ mục trực tiếp theo giá trị nguyên, không theo offset hay index nào. Khoảng constraint (-10^9 đến 10^9) loại bỏ array-indexed approach nhưng không ảnh hưởng gì đến hash set. set của Python và HashSet<int> của C# xử lý số nguyên âm y hệt số nguyên dương.

Mảng lớn không có duplicate [1, 2, ..., 10^5]: trường hợp xấu nhất cho hash set — nó phình ra đến 10^5 phần tử trước khi trả về false. Đây là lúc chi phí O(n) bộ nhớ trở nên rõ ràng, nhưng vẫn đúng và nhanh hơn nhiều so với brute force O(n^2).

Nhận diện pattern

Seen set là cấu trúc dữ liệu phổ biến nhất trong các bài toán array membership. Khi nào câu hỏi là "tôi đã thấy cái này chưa?", set trả lời trong O(1). Các từ khoá báo hiệu điều này: "duplicate", "appears twice", "at least twice", "distinct", "unique elements".

Pattern tổng quát hoá theo hai hướng từ đây. LeetCode 219 (Contains Duplicate II) thêm window constraint: "có duplicate nào trong k vị trí liên tiếp không". Cách sửa là giữ set có giới hạn — loại bỏ phần tử ra ngoài cửa sổ trước khi kiểm tra cái mới. LeetCode 220 (Contains Duplicate III) thêm value proximity constraint lên trên window: "có hai giá trị cách nhau tối đa t trong k vị trí không". Hash set đơn thuần không đủ ở đó vì bạn cần range query; bạn cần sorted structure như balanced BST hoặc sorted list.

Reflex cốt lõi vẫn như nhau ở cả ba. Cấu trúc dữ liệu xung quanh set thay đổi để phù hợp với constraint bổ sung.

Vị trí trong series

Two Sum (bài trước) cần một map — value -> index — vì sau khi xây dựng cấu trúc seen bạn cần lấy lại chỉ số nào có complement target - x. Bài này chỉ cần membership: giá trị này đã xuất hiện chưa? Set đơn thuần là đủ. Cùng một reflex, cấu trúc đơn giản hơn.

Bước tiếp theo là Valid Anagram, nơi câu hỏi mở rộng từ "đã thấy giá trị này chưa?" thành "hai chuỗi có cùng tần số ký tự không?" Điều đó cần đếm, nên map trở lại — nhưng lần này map character -> frequency thay vì value -> index. Cùng họ bài toán, thêm chút số học, thêm một trường mỗi phần tử.

Các bài liên quan

• 219. Contains Duplicate II — cùng bài toán nhưng có window constraint về khoảng cách chỉ số; set trở thành bounded
• 220. Contains Duplicate III — window về khoảng cách chỉ số cộng thêm value proximity; cần sorted structure cho range query
• 287. Find the Duplicate Number — tìm giá trị bị lặp cụ thể trong [1, n]; biến thể bị giới hạn bộ nhớ dùng Floyd's cycle detection
• 442. Find All Duplicates in an Array — báo cáo mọi giá trị xuất hiện đúng hai lần; dùng sign-flip trick để đánh dấu index đã thăm in-place