Задача: проверить массив на дубликаты
2026-02-21 01:42 Diff
https://skillbox.ru/media/code/zadacha-proverit-massiv-na-dublikaty/

#статьи

  • 23 янв 2023
  • 0

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

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

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

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

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

Ввод: nums = [1,2,3,1] Вывод: true Ввод: nums = [1,2,3,4] Вывод: false Ввод: 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; }

Результаты

Временная сложность: O(n) — так как в самом плохом случае мы проходимся по всему массиву.

Ёмкостная сложность: O(1) — нам нужно заранее определённое количество места в памяти.


Научитесь: Профессия Java-разработчик + ИИ Узнать больше