# Array - 219. Contains Duplicate II

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 absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

java：

``````class Solution {

// solution 1 hashmap. time: O(n) space: O(n)
/*public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length == 0) return false;

HashMap<Integer, Integer> map = new HashMap();
for (int i = 0;  i < nums.length; i++) {
Integer index = map.get(nums[i]);
if (index != null && i-index <= k){
return true;
}

map.put(nums[i], i);
}

return false;
}*/

// solution 2 Sliding Window. time: O(n) space: O(k)
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length == 0) return false;

HashSet<Integer> set = new HashSet();
for (int i = 0;  i < nums.length; i++) {
return true;
}

// 更新set，保证大小不超过k
if (i >= k) {
set.remove(nums[i - k]);
}
}

return false;
}

} // best case

``````

go：

``````
/*func containsNearbyDuplicate(nums []int, k int) bool {
if nums == nil || len(nums) == 0 { return false }

var (
maps   = make(map[int]int)
window = make([]int, 0)
)

for i, v := range nums {
if _, ok := maps[v]; ok{
return true
} else {
maps[v] = i
window = append(window, v)
}

// update map size if we have more than k
if (i >= k) {
delete(maps, window[0])
window = window[1:]
}
}

return false
}

func containsNearbyDuplicate(nums []int, k int) bool {
exist := make(map[int]int, len(nums))
for i, v := range nums{
if pos, ok := exist[v]; ok && i - pos <= k{
return true
}
exist[v] = i
}
return false
}`````````

Nothing just happens, it's all part of a plan.