Задача: проверить массив на дубликаты

Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня ищем в массиве повторяющиеся элементы.

Иллюстрация: Polina Vari для Skillbox Media

Дмитрий Зверев

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Сергей Голицын

Senior Java Developer в Covalent Inc. и преподаватель. Больше семи лет в Java-разработке. В свободное время судит хакатоны и делится опытом с начинающими программистами. Пишет статьи для «Хабра» и Medium. Ведёт телеграм-каналы «Полезные ссылки около Java» и Cracking code interview.

Условие. Дан массив целых чисел — nums. Необходимо написать функцию, которая возвращает true, если в этом массиве хотя бы одно число повторяется дважды. Если же все элементы уникальны, функция должна вернуть false.

Ввод и вывод. Пример 1

Ввод: nums = [1,2,3,1]
Вывод: true

Пример 2

Ввод: nums = [1,2,3,4]
Вывод: false

Пример 3

Ввод: nums = [1,1,1,3,3,4,3,2,4,2]
Вывод: true

Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из телеграм-канала Сергея Cracking code interview.

Решение

При решении подобных задач важно выбрать подходящий тип данных. Здесь мы исходим из такой логики: «повторяется дважды» → значит, ищем дубликаты. Следовательно, выбираем множество (set).

Мы создадим пустое множество и будем обходить весь массив, просто проверяя, находится ли элемент во множестве:

если он ещё не находится — добавляем его;
если элемент уже там — значит, мы встретили повторяющийся элемент и просто возвращаем true.

public boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int i : nums) {
        if (set.contains(i)) {
            return true;
        } else {
            set.add(i);
        }
    }
    return false;
}