Problem 219: Contains Duplicate II
思路
这道题用 HashMap 来存元素
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (hm.containsKey(nums[i])) {
int diff = i - hm.get(nums[i]);
if (diff <= k) {
return true;
} else {
hm.put(nums[i], i);
}
} else {
hm.put(nums[i], i);
}
}
return false;
}
}
键值对谁是键谁是值
hm.put(nums[i], i);
因为这样便于定位元素的 index
这道题 tricky 的一点就是,当发现重复元素以后,有可能超过 k,但是!后面可能还有重复元素,不能直接退出
eg: [1 0 1 1],k = 1. 这时,后面两个 1 是满足条件的,所以我们要多一个判断
int diff = i - hm.get(nums[i]); if (diff <= k) { return true; } else { hm.put(nums[i], i); }
Last updated
Was this helpful?