正文
LeetCode OJ：Contains DuplicateII（是否包含重复II）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
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 difference between i and j is at most k .
这题上上一篇博客的延伸，问的是k长的距离内有没有两个数是相等的，类似一个滑动窗口问题，方法比较简单，使用一个map记下上次数出现的位置就可以了，代码如下：
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
map<int, int> ret;
int sz = nums.size();
for (int i = ; i < sz; ++i){
if (ret.find(nums[i]) != ret.end() && i - ret[nums[i]] <= k)
return true;
else
ret[nums[i]] = i;
}
return false;
}
};
java版本的代码如下所示，用的方法都是一样的：
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; ++i){
if(m.containsKey(nums[i]))
if(i-m.get(nums[i]) <= k)
return true;
m.put(nums[i], i);//放在这里有两个原因，如果本来存在将index更新到最近的位置，如果不存在就将它放到map中起
}
return false;
}
}
