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.
思路:用哈希表记录数字对应的位置,遍历数组,如果哈希表中已存在此数字,更新相距的最短距离,如果最短距离小于等于k,则返回true。
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (k < 1) {
return false;
}
//record num => pos
HashMap<Integer, Integer> map = new HashMap<>();
//min distance
int minDistance = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
minDistance = Math.min(minDistance, i - map.get(nums[i]));
if (minDistance <= k) {
return true;
}
}
map.put(nums[i], i);
}
return false;
}
网友评论