Phát Hiện Phần Tử TrùngContains Duplicate
Hiểu bài
Cho bạn một mảng số nguyên nums. Trả về true nếu có bất kỳ phần tử nào xuất hiện ít nhất 2 lần. Trả về false nếu tất cả phần tử đều khác nhau.
Ví dụ:
nums = [1, 2, 3, 1]
output = true // vì 1 xuất hiện 2 lần
nums = [1, 2, 3, 4]
output = false // tất cả phần tử đều khác nhauBài này là kiểm tra cơ bản về khả năng dùng Hash Map để theo dõi phần tử đã thấy.
Xem cách cơ bản (chậm hơn)
O(n²) time, O(1) spacefunction 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
}Mỗi phần tử được so sánh với tất cả phần tử còn lại.
Cách này dùng ít bộ nhớ nhưng rất chậm khi n lớn.
Lời giải tối ưu
O(n) time, O(n) spacefunction containsDuplicate(nums: number[]): boolean {
const seen = new Set<number>()
for (const num of nums) {
if (seen.has(num)) return true
seen.add(num)
}
return false
}Dùng Set thay Hash Map vì chỉ cần biết phần tử đã xuất hiện chưa, không cần lưu chỉ số.
- Đây là cách tối ưu nhất: mỗi bước insert và lookup đều O(1) amortized.
- Gặp phần tử đã có trong Set → dừng ngay, không duyệt hết mảng.
Chạy thử từng bước
- 1
num=1. seen rỗng, chưa có 1 → thêm 1 vào seen.
num:1seen:[1] - 2
num=2. seen={1}, chưa có 2 → thêm 2.
num:2seen:[1,2] - 3
num=3. seen={1,2}, chưa có 3 → thêm 3.
num:3seen:[1,2,3] - 4
num=1. seen={1,2,3}, đã có 1 → return true ngay.
num:1seen:[1,2,3]found:true
Trường hợp biên phải nhớ
Mảng rỗng — không có phần tử nào, return false.
Mảng 1 phần tử — không thể có trùng, return false.
Tất cả phần tử giống nhau [5, 5, 5] — phát hiện ngay ở phần tử thứ 2.
Số âm và số 0 — Set xử lý đúng với mọi số nguyên, kể cả âm.