Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
Example 1:
Input: [1,2,3,1], k = 3
Output: true
Example 2:
Input: [1,0,1,1], k = 1
Output: true
Example 3:
Input: [1,2,1], k = 0
Output: false
Solution:
public boolean containsNearbyDuplicate(int[] nums, int k) {
if(nums==null||k<1) return false;
Map<Integer,Integer> hash=new HashMap<>();
for(int i=0;i<nums.length;i++){
if(hash.containsKey(nums[i])){
if(i-hash.get(nums[i])<=k){
return true;
}
}
hash.put(nums[i],i);
}
return false;
}
时间复杂度：O(n)
空间复杂度：O(n)
哈希表的题。和Two Sum比较像，哈希表记录元素的值作为key，value用数组下标，当key一样是检查下标是否符合<=k。
有的人提议用滑动窗口做，我觉得思路挺新颖的，k是窗口大小，在窗口内若存在相等值即返回true。
