问题描述：
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。如果存在两个数相等，其下标的间隔小于等于k，就返回true。否者 返回false。
代码实现：
public boolean
containsNearbyDuplicate(
int[] nums,
int k) {
if (nums ==
null || nums.length <=
1) {
return false;
}
Map<Integer, Integer> keyLocationsMap =
new HashMap<Integer, Integer>();
for (
int i =
0; i < nums.length; i++) {
if (keyLocationsMap.
get(nums[i]) !=
null) {
if ((i - keyLocationsMap.
get(nums[i])) <= k) {
return true;
}
}
keyLocationsMap.put(nums[i], i);
}
return false;
}
问题改进：
在上面解法中，使用了一个hashmap来存放一个数的值和下标，当值相等是，然后比较下标。如果下标超过了需要等下下标。可以使用一个hashSet，值存放当前下标之前的k个数，之前的数全部删除。
代码实现：
public boolean containsNearbyDuplicate(
int[] nums,
int k) {
Set<Integer> containsSet =
new HashSet<Integer>(k );
for (
int i =
0; i < nums.length; i++) {
if (i > k) {
containsSet.remove(nums[i - k -
1]);
}
if (!containsSet.add(nums[i])) {
return true;
}
}
return false;
}
总结
将一个问题限定在一定的范围内，设定边界是一种很好的方法。
