219. 存在重复元素 II
Solution
思路1:
重复元素 然后就用HashMap不断更新最新出现的位置 与k值判断即可。
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> mp = new HashMap<>();
int len = nums.length;
for (int i = 0; i < len; i++) {
if (mp.containsKey(nums[i])) {
int idx = mp.get(nums[i]);
if (Math.abs(i - idx) <= k) {
return true;
} else {
mp.put(nums[i], i);
}
} else {
mp.put(nums[i], i);
}
}
return false;
}
}
思路2:
涉及下标和区间大小的就往滑动窗口想一想!不够k个就一直塞,够k个就判断一下重复不(可以用Set判断),然后删一个,继续。
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> st = new HashSet<>();
int len = nums.length;
for (int i = 0; i < len; i++) {
if (i > k) {
st.remove(nums[i - k - 1]);
}
if (!st.add(nums[i])) {
return true;
}
}
return false;
}
}