题目:
给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的 绝对值 至多为 k。
解题思路:这道题有三种解法:暴力,滑动窗口,Set。
暴力解法:循环遍历数组,判断是否nums[i]==nums[j],根据题目意思还得加个判断条件i下标减去j下标的绝对值要小于等于给定的k。但是提交上去的话会超出时间限制,但是把第二个条件加在第二个for循环里面就不会超出时间限制。
滑动窗口:分别设置left和right,先让left不动,让right先往后遍历,看是否nums[left]==nums[right],并且如果left-right>k,则要移动left
Set:遍历数组,判断如果数组里面包含当前数组返回true,如果不包含则把当前元素添加进去。判断如果set中的元素数量大于k,则将前面的元素移除。
代码实现:
暴力解法:
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
for (int i = 0; i < nums.length ; i++) {
for (int j = i+1; j<=k+i&&j < nums.length ; j++) {
if (nums[i]==nums[j]){
return true;
}
}
}
return false;
}
}
Set解法:
class solution{
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new TreeSet<>();
for (int i = 0; i < nums.length; ++i) {
if (set.contains(nums[i])) return true;
set.add(nums[i]);
if (set.size() > k) {
set.remove(nums[i - k]);
}
}
return false;
}
}