How to solve the problem of duplicate elements in leetcode
This article mainly introduces how to solve the problem of repetitive elements in leetcode. It is very detailed and has a certain reference value. Interested friends must read it!
Topic link
Https://leetcode-cn.com/problems/contains-duplicate-ii/
Topic description
Given an array of integers and an integer k, it is determined whether there are two different indexes I and j in the array, such that nums [I] = nums [j], and the absolute value of the difference between I and j is maximum k.
Example 1:
Input: nums = [1, 2, 2, 3, 1], k = 3
Output: true
Example 2:
Input: nums = [1j0pr 1pl], k = 1
Output: true
Example 3:
Input: nums = [1, 2, 3, 1, 1, 2, 3], k = 2
Output: false
The idea of solving the problem
Tag: hash
Maintain a hash table that always contains at most k elements. When a duplicate value occurs, it indicates that there are duplicate elements within the k distance.
Traversing one element at a time adds it to the hash table, and removes the first number if the size of the hash table is greater than k
Time complexity: O (n), n is the length of the array
Code
Java version
Class Solution {
Public boolean containsNearbyDuplicate (int [] nums, int k) {
HashSet set = new HashSet ()
For (int I = 0; I
< nums.length; i++) { if(set.contains(nums[i])) { return true; } set.add(nums[i]); if(set.size() >K) {
Set.remove (Nums [I-k])
}
}
Return false
}
}
JavaScript version
/ * *
* @ param {number []} nums
* @ param {number} k
* @ return {boolean}
, /
Var containsNearbyDuplicate = function (nums, k) {
Const set = new Set ()
For (let I = 0; I
< nums.length; i++) { if(set.has(nums[i])) { return true; } set.add(nums[i]); if(set.size >K) {
Set.delete (Nums [I-k])
}
}
Return false
}
Drawing and interpretation
The above is all the content of this article entitled "how to solve the problem of repetitive elements in leetcode". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!
