地址
难度
简单
题目
给你一个整数数组nums和一个整数k，判断数组中是否存在两个 不同的索引i和j，满足nums[i] == nums[j] 且 abs(i-j) <= k。如果存在，返回true；否则，返回false 。
示例 1：
输入：nums = [1,2,3,1], k = 3
输出：true
示例 2：
输入：nums = [1,0,1,1], k = 1
输出：true
示例 3：
输入：nums = [1,2,3,1,2,3], k = 2
输出：false
提示：
* 1 <= nums.length <= 10^5
* -10^9 <= nums[i] <= 10^9
* 0 <= k <= 10^5
思路
- 暴力破解
双重 for 循环。判断是否存在相同的值并且其索引的绝对值小于等于 K
时间复杂度 O(n^2)，空间复杂度 O(1)。不过在 Leetcode 上执行的时候。提示超时时间限制
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j] && Math.abs(i - j) <= k) {
return true;
}
}
}
return false;
}
}
- HashMap
在 hashMap 中有一个containsKey方法，即判断是否包含指定的键名。
利用 for 循环数组，发现有重复的数值，则将其索引和 hashMap 存储的索引相减，看其绝对值是否小于等于 K
时间复杂度 O(n)，空间复杂度 O(n)。
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer,Integer> map =new HashMap<>();
for(int i =0;i<nums.length;i++){
if(map.containsKey(nums[i])){
int x = map.get(nums[i]);
if(Math.abs(x-i)<=k){
return true;
}
}
map.put(nums[i],i);
}
return false;
}
}
- HashSet
维护一个哈希表，里面始终最多包含 k 个元素，当出现重复值时则说明在 k 距离内存在重复元素。每次遍历一个元素则将其加入哈希表中，如果哈希表的大小大于 k，则移除最前面的数字
时间复杂度：O(n)，n为数组长度
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashSet<Integer> set =new HashSet<>();
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;
}
}