By Long Luo

This article is the solution of Problem 219. Contains Duplicate II.

# Brute Force

Easy, using 2 loops to determine whether there is the same number.

obviously, it will time out.

## Analysis

• Time Complexity: $O(n^2)$
• Space Complexity: $O(1)$

# HashMap

We use a HashMap to record the maximum index of each element. When scanning the array from left to right, the process:

• If an element $\textit{nums}[i]$ already exists in the hash table and the index $j$ of the element recorded in the hash table satisfies $ij \le k$, return $\text{true}$;

• Recording $\textit{nums}[i]$ and index $i$ into the hash table, where $i$ is the largest index of $\textit{nums}[i]$.

The order of the above two-step operations cannot be changed, when the index $i$ is traversed, the element equal to the current element and the maximum index of the element can only be found in the elements before the index $i$.

## Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

# Sliding Window

Maintain a sliding window whose length does not exceed $k+1$ in the array $\textit{nums}$, and the abs value of any two index delta in the same sliding window does not exceed $k$.

If the sliding window has repeated elements, then there are two different index $i$ and $j$ such that $\textit{nums}[i] = \textit{nums}[j]$ and $i - j \le k$.

If there are no repeating elements in the sliding window, there is no index that meets the requirements.

Therefore, it is only necessary to traverse each sliding window and determine whether there are duplicate elements in the sliding window.

We use a HashSet to store the elements in the sliding window.

If $i > k$, the element whose index is $i-k-1$ will be removed from the sliding window.

If a element already exists in the HashSet, there are duplicate elements, return $\textit{true}$, if not in the hash set add it to the hash set.

## Analysis

• Time Complexity: $O(n)$.
• Space Complexity: $O(k)$.

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗