# LeetCode Notes: Contains Duplicate II

## Question

Given an integer array `nums`

and an integer `k`

, return `true`

if there are two **distinct indices** `i`

and `j`

in the array such that `nums[i] == nums[j]`

and `abs(i - j) <= 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

**Example 3:**

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

Output:false

**Constraints:**

- 1 <= nums.length <= 10
^{5} - -10
^{9}<= nums[i] <= 10^{9} - 0 <= k <= 10
^{5}

## Solution One

**Analysis:**

Use an object to store the information of each number, using the principle that the key cannot be repeated, each time a new repeated number is encountered, the position information and the absolute value of the most recent repeated number are updated. Once an absolute value is smaller than `k`

it is to successfully find the number you want.

**Code:**

```
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var containsNearbyDuplicate = function(nums, k) {
// Initialize storage space
const obj = {};
// Just loop once, traverse all the numbers
for(let i = 0; i < nums.length; i++){
// current number
const n = nums[i]
// Whether there are duplicate numbers
if(n in obj){
// For repeated numbers, the absolute value needs to be updated to the difference with the previous value, because the difference with the previous one must be smaller
obj[n].abs = i-obj[n].i;
// After calculating the difference above, you can update the current position, which is used to calculate the difference when it repeats the next time
obj[n].i = i;
// Once the current difference is found to be less than k, the condition is met and exit
if(obj[n].abs <= k) return true;
}else{
// Initialize the number that appears for the first time, store the location and absolute value (because it appears for the first time, the absolute value is 0)
obj[n] = {
i:i,
abs:0
}
}
}
//If the number that meets the conditions is not found in the above loop, it will return `false` by default
return false
};
```

## Solution Two

**Analysis:**

Make use of the feature of `Set`

that no repeated elements are allowed, make a sliding window of `k`

size, and slide forward to find whether the same element appears in the window. This sliding window requires less space.

**Code:**

```
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var containsNearbyDuplicate = function(nums, k) {
const set = new Set();
for(let i = 0; i < nums.length; i++){
// Once repeated elements appear in the sliding window, the requirements are met
if(set.has(nums[i])){
return true
}
// Every value is added
set.add(nums[i]);
// Once the number exceeds k, delete the first number, that is, the sliding window moves to the right
if(set.size> k){
set.delete(nums[i-k]);
}
}
return false
};
```

## Comments