LeetCode - Contains Duplicate II
Problem description
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 absolute difference between i and j is at most k.
Example 1:
1
2
Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:
1
2
Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:
1
2
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
Analysis
The first thought is to use HashMap to store all index of the same value and test if the there’s an index is differ from the current index within k.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0 ; i< nums.length; i++){
List<Integer> list = map.getOrDefault(nums[i], new ArrayList());
if (list.size() != 0){
for (int pre:list){
if (Math.abs(pre-i) <= k){
return true;
}
}
}
else{
map.put(nums[i], list);
}
list.add(i);
}
return false;
}
}
However, this solution is bad. We can use a HashSet to maintain a sliding window of size k.
1
2
3
4
5
6
7
8
9
10
11
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;
}
An improvement of approach 1 is to save the next i but not all the index.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer,Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (!hashMap.containsKey(nums[i])){
hashMap.put(nums[i],i);
}else {
Integer index = hashMap.get(nums[i]);
if (k >= (i - index)){
return true;
}else {
hashMap.put(nums[i],i);
}
}
}
return false;
}
}