219. 存在重复元素 II

题目

给你一个整数数组 nums 和一个整数 k ,判断数组中是否存在两个 不同的索引 ij ,满足 nums[i] == nums[j]abs(i - j) <= k 。如果存在,返回 true ;否则,返回 false

示例1:

1
2
输入: nums = [1,2,3,1], k = 3
输出: true

示例2:

1
2
输入: nums = [1,0,1,1], k = 1
输出: true

示例3:

1
2
输入: nums = [1,2,3,1,2,3], k = 2
输出: false

提示:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105

解法

解法一:

遍历数组,假设当前数字索引为i,那么计算从i+1 到i+k是否有其相同的元素,有返回true,否则继续判断下一个数字

Java

1
2
3
4
5
6
7
8
9
10
11
12
public boolean containsNearbyDuplicate(int[] nums, int k) {
for (int i = 0;i < nums.length;i++) {
int count = 1;
while (count <= k && i + count < nums.length) {
if (nums[i] == nums[i + count]) {
return true;
}
count++;
}
}
return false;
}

解法二:

借助HashMap。

遍历数组,在遍历的过程中,判断该数字是否已经存在HashMao中了。

如果已经存在,挨个计算它之前的索引和当前索引差是否超过k,没有则返回true;

否则把当前索引加入索引列表中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, List<Integer>> map = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
List<Integer> list = map.get(nums[i]);
for (int num : list) {
if (k >= Math.abs(num - i)) {
return true;
}
}
map.get(nums[i]).add(i);
} else {
List<Integer> list = new ArrayList<>();
list.add(i);
map.put(nums[i], list);
}
}
return false;
}

解法三:

使用HashSet。

遍历数组,对于每个元素做以下操作:

  1. 在散列表中搜索当前元素,如果找到了就返回 true
  2. 在散列表中插入当前元素。
  3. 如果当前散列表的大小超过了 kkk, 删除散列表中最旧的元素。

返回false

1
2
3
4
5
6
7
8
9
10
11
12
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<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;
}

0%