如果采用二重遍历会超时，所以需要用一些数据结构优化：
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set= new HashSet<Integer>();
for(int i=0;i<nums.length;i++){
if(i>k) set.remove(nums[i-k-1]); //只保留k+i - i + 1个元素
if(!set.add(nums[i])) //在此范围内加入重复的元素add会返回false
return true;
}
return false;
}
}
- Set集合里多个对象之间没有明显的顺序
- Set集合不允许重复元素,HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode（）方法返回值也相等。
A
Setrepresents a generic "set of values". ATreeSetis a set where the elements are sorted (and thus ordered), aHashSetis a set where the elements are not sorted or ordered. AHashSetis typically a lot faster than aTreeSet.
ATreeSetis typically implemented as ared-black tree, whereas aHashSetusesObject.hashCode()to create an index in an array. Access time for a red-black tree isO(log(n))whereas access time for a HashSet ranges fromconstant-timeto the worst case (every item has the same hashCode) where you can have a linear search time O(n).
