导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一
    2. 方法二

LeetCode-219.Contains Duplicate II

题目

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

翻译

给出一个整型数组和一个整数k,判断是否存在不同的下标i和j,使得nums[i] = nums[j]并且i与j的差不比k大。

方法一

设立一个set,用来记录目前已有元素,判断是否重复。
设立左右两个游标,同时指向第一个元素。右游标不断后移,存入前k个元素,在过程中判断是否重复,如果有重复直接返回,如果没有左右同时后移,保证差为k,同时从set中去除左元素,加入右元素并判断是否重复。
需要注意k比nums长度大的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> numsSet = new HashSet<Integer>();
int left = 0, right = 0, len = nums.length;

while (right < len && right - left <= k) {
if (numsSet.contains(nums[right]))
return true;
numsSet.add(nums[right++]);
}

while (right < len) {
numsSet.remove(nums[left++]);
if (numsSet.contains(nums[right]))
return true;
numsSet.add(nums[right++]);
}

return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> numsSet = new HashSet<Integer>();

for (int i = 0; i < nums.length; i++) {
if (i > k)
numsSet.remove(nums[i - k - 1]);
if (!numsSet.add(nums[i]))
return true;
}

return false;
}

方法二

设立一个map,记录每个下标和数字,循环判断是否已经出现并且下标差不大于k。

1
2
3
4
5
6
7
8
9
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> numsMap = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (numsMap.containsKey(nums[i]) && i - numsMap.get(nums[i]) <= k)
return true;
numsMap.put(nums[i], i);
}
return false;
}