Easy задача с собеседования в Facebook: Contains Duplicate ||
Tags: interview, algorithms, faang
Published: 2024-07-03 11:59:08

## Задача.
Дан массив целых чисел nums и число k. Нужно вернуть true, если в массиве есть два уникальных индекса i и j, такие что nums[i] == nums[j] и abs(i-j)<=k.
Ссылка на leetcode: https://leetcode.com/problems/contains-duplicate-ii/

Примеры:
Input: nums = [1,2,3,1], k = 3
Output: true

nums[0] == nums[3] abs(3-0) <= k

Input: nums = [1,2,3,1,2,3], k = 2
Output: false
Одинаковые элементы есть, но расстояние между ними больше 2.

## Решение.

Переформулируем задачу более понятным языком:

> Нам нужно проверить, есть ли среди элементов массива повторяющиеся элементы, которые находятся на расстоянии меньше или равном 
> k друг от друга.

### Brute force
Очевидное решение, которое приходит в голову - это сравнить все пары элементов в массиве, если они равны, вычислить расстояние между ними по индексам, если это расстояние меньше или равно k - вернуть true.

**Как перебрать все возможные пары элементов в массиве?**
**Ответ**: двумя вложенными циклами, причем вложенный цикл будет не от нуля, а от i + 1, чтобы не сравнивать элементы сами с собой, а также не перебирать одни и теже пары два раза (вроде пар (nums[1], nums[2]) и (nums[2], nums[1]), т.к. это по сути та же самая пара):

```java
for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        //проверяем пару nums[i] и nums[j]
    }
```

Дополним этот код проверкой, что у нас элементы пары равны между собой и расстояние между ними меньше или равно k:

```java
public boolean containsNearbyDuplicate(int[] nums, int k) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] == nums[j] && j - i <= k) {
                return true;
            }
        }
    }
    return false;
}
```
Временная сложность такого решения - **O(n^2)**, т.к. у нас 2 вложенных цикла по массиву. Сложность по памяти - **O(1)**.

**Sliding Window**
Можем ли мы улучшить наше решение по временной сложности? Да, мы можем применить подход, который называется **Sliding Window (скользящее окно).**
Для этого нам нужно заметить, что нас интересует **наличие дубликата на расстоянии меньше или равном k от произвольного текущего элемента массива.** Т.е. мы можем **всего один раз проитерироваться** по массиву и хравнить в памяти для быстрого доступа только k предыдущих элементов массива.
Например, для массива:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/m4igquij8g3hbh9y5jxx.png)

и k = 3, будем хранить предыдущие 3 элемента массива в некой структуре данных (скользящем окне).
Допустим, при итерациях вдоль массива мы достигли элемента с индексом i = 3:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/k6oqrb3uzl87srh2lku4.png)

Тогда в Sliding Window мы будем хранить предыдущие 3 элемента массива. Нам нужно проверить, есть ли текущий элемент среди элементов помещенных в Sliding Window. Если есть, то нужно вернуть true в качестве результата работы функции. Если нет, то перейдем к следующей итерации цикла и обновим Sliding Window, чтобы хранить там предыдущие 3 элемента массива:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jwc6e5ruik2vl1w5x93e.png)
И снова нам нужно повторить проверку, есть ли среди элементов в Sliding Window текущий элемент. В данном случае есть - поэтому вернем true.

Хорошо, алгоритм понятен. Как нам реализовать это в коде?
Т.к. нам нужно **иметь возможность быстро проверить наличие или отсутствие элемента в Sliding Window**, нам нужно использовать **что-то типа HashMap**. Но в данном случае нам будет достаточно **HashSet**, т.к. нам надо хранить только ключи, без значений.

```java
Set<Integer> slidingWindow = new HashSet<>();
```
По мере итераций, нам надо удалять из Sliding Window самый первый элемент и добавлять текущий. Самый первый элемент, это элемент на расстоянии k от текущего. 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5v0jps30n6en07dt7vm9.png)


Тогда получим:

```java
Set<Integer> slidingWindow = new HashSet<>();

for(int i = 0 ; i < nums.length; i++) {
    //удаляем первый элемент
    //элемент на расстоянии k по индексам от текущего
    slidingWindow.remove(nums[i - k - 1]);
    ...
    //Добавляем текущий/новый элемент
    slidingWindow.add(nums[i]);
}
```
Т.к. мы вычисляем элемент на расстоянии k от текущего по формуле i - k - 1, то нам надо добавить проверку, чтобы мы не вышли за пределы массива:

```java
for(int i = 0 ; i < nums.length; i++) {
    if (i > k) {
        slidingWindow.remove(nums[i - k - 1]);
    }
    ....
    slidingWindow.add(nums[i]);
}
```
В таком виде, Sliding Window будет хранить только k предыдущих элементов массива. Теперь осталось только добавить проверку, что в Sliding Window есть текущий элемент:

```java
public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> slidingWindow = new HashSet<>();
    for(int i = 0 ; i < nums.length; i++) {
        if (i > k) {
            slidingWindow.remove(nums[i - k - 1]);
        }
        if (slidingWindow.contains(nums[i])) {
            return true;
        }
        slidingWindow.add(nums[i]);
    }
    return false;
}
```
Временная сложность такого решения - **O(n)**. Сложность по памяти - **O(k)**, т.к. мы дополнительно храним k предыдущих элементов в Sliding Window.