219. Contains Duplicate II
Tags:
Easy
Skills:
Hashmap
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
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] Approach - Hash map
prev_index ∣i−prevIndex |≤ k thì trả về true.Time and space complexity
Solution
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};trueApproach - sliding window với hash set
true Time and space complexity
Solution
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};i , cửa sổ của bạn nên chỉ chứa các phần tử từ i - k + 1 đến ik+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.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