Easy задача с собеседования в Facebook: Contains Duplicate ||

Задача.

Дан массив целых чисел 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]), т.к. это по сути та же самая пара):

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

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

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 предыдущих элементов массива.
Например, для массива:

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

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

И снова нам нужно повторить проверку, есть ли среди элементов в Sliding Window текущий элемент. В данном случае есть – поэтому вернем true.

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

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

По мере итераций, нам надо удалять из Sliding Window самый первый элемент и добавлять текущий. Самый первый элемент, это элемент на расстоянии k от текущего.

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

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, то нам надо добавить проверку, чтобы мы не вышли за пределы массива:

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 есть текущий элемент:

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.