219. Contains Duplicate II

Problem

Bài toán yêu cầu kiểm tra trong mảng số nguyên nums có tồn tại hai chỉ số khác nhau i và j sao cho

nums[i] === nums[j]

|i - j| ≤ k

Approach - Hash map

Duyệt qua từng phần tử trong mảng

Với mỗi giá trị, kiểm tra nếu nó đã xuất hiện trước đó ở chỉ số prev_index

Nếu ∣i−prevIndex |≤ k thì trả về true.

Cập nhật lại chỉ số cuối cùng mà giá trị này xuất hiện

Time and space complexity

TC: O(n)

SC: O(n), trường hợp tệ nhất (không có phần tử nào trùng lặp)

Solution

typescripttypescript

1function containsNearbyDuplicate(nums: number[], k: number): boolean {
2	const index_map: Map<number, number> = new Map();
3	for(let i = 0; i < nums.length; i++) {
4		if(index_map.has(nums[i]) {
5			const prev_index = index_map.get(nums[i]);
6			if(i - prev_index <= k) {
7				return true
8			}
9		}
10		index_map.set(nums[i], i);
11	}
12	
13	return false;
14};

💡

Ý tưởng: Lưu lại chỉ số cuối cùng xuất hiện của giá trị. Nếu tìm thấy phần tử trùng và khoảng cách chỉ số không vượt quá k, return true

Approach - sliding window với hash set

Duy trì một sliding window kích thước tối đa k phần tử gần nhất

Nếu phần tử hiện tại đã có trong window, return true

Nếu window vượt quá k, loại bỏ phần tử cũ nhất ra khỏi cửa sổ

Time and space complexity

TC: O(n)

SC: O(min(n, k)) sliding window chỉ lưu tối đa k phần tử, (nếu k > n thì là O(n), còn lại là O(k))

Solution

typescripttypescript

1function containsNearbyDuplicate(nums: number[], k: number): boolean {
2    const word_set: Set<number> = new Set();
3    for (let i = 0; i < nums.length; i++) {
4        if (word_set.has(nums[i])) {
5            return true;
6        }
7        word_set.add(nums[i])
8        if (word_set.size > k) {
9            word_set.delete(nums[i - k])
10        }
11    }
12
13    return false;
14};

💡

Tại sao lại là i - k?

Khi bạn đang ở vị trí i , cửa sổ của bạn nên chỉ chứa các phần tử từ i - k + 1 đến i

Nếu bạn thêm phần tử thứ k+1 vào cửa sổ, phần tử ở vị trí i-k sẽ nằm ngoài phạm vi cho phép (vì |i - (i-k)| = k nhưng nếu xét tiếp theo sẽ thành k+1), nên cần loại bỏ nó để giữ đúng kích thước cửa sổ là k phần tử gần nhất.

Cụ thể, khi i >= k, bạn gọi window_set.delete(nums[i - k]) để loại bỏ phần tử cũ nhất trong cửa sổ, đảm bảo chỉ kiểm tra trùng lặp trong phạm vi k chỉ số gần nhất.

Minh họa

Giả sử k = 3, khi bạn ở i = 4, cửa sổ sẽ chứa các phần tử ở vị trí 1, 2, 3, 4. Để duy trì kích thước cửa sổ là 3, bạn cần loại bỏ phần tử ở vị trí i - k = 1 trước khi xét tiếp.

Tóm lại:

window_set.delete(nums[i - k]) giúp cửa sổ trượt luôn chứa đúng tối đa k phần tử gần nhất, đảm bảo kiểm tra đúng điều kiện |i - j| <= k như đề bài yêu cầu

Loading content...

1function containsNearbyDuplicate(nums: number[], k: number): boolean { 2 const index_map: Map<number, number> = new Map(); 3 for(let i = 0; i < nums.length; i++) { 4 if(index_map.has(nums[i]) { 5 const prev_index = index_map.get(nums[i]); 6 if(i - prev_index <= k) { 7 return true 8 } 9 } 10 index_map.set(nums[i], i); 11 } 12 13 return false; 14};

1function containsNearbyDuplicate(nums: number[], k: number): boolean { 2 const word_set: Set<number> = new Set(); 3 for (let i = 0; i < nums.length; i++) { 4 if (word_set.has(nums[i])) { 5 return true; 6 } 7 word_set.add(nums[i]) 8 if (word_set.size > k) { 9 word_set.delete(nums[i - k]) 10 } 11 } 12 13 return false; 14};