Опишите интересную техническую задачу, которую вы решали, и ваше решение

Задача: Оптимизировать поиск дубликатов в большом массиве целых чисел, сократив временную сложность с O(n²) до O(n).

Исходная проблема: Наивное решение с двумя вложенными циклами для массива из n элементов выполняет n*(n-1)/2 сравнений, что неприемлемо для больших данных.

Решение: Использовать HashSet для отслеживания уже встреченных элементов. HashSet обеспечивает константное время выполнения add() и contains() в среднем случае (O(1)).

Реализация алгоритма:

import java.util.*;

public List<Integer> findDuplicates(int[] nums) {
    // Set для хранения уникальных элементов, которые мы уже видели
    Set<Integer> seen = new HashSet<>();
    // List для результата — найденных дубликатов
    List<Integer> duplicates = new ArrayList<>();

    for (int num : nums) {
        // Метод add() возвращает false, если элемент УЖЕ присутствует в множестве
        if (!seen.add(num)) {
            duplicates.add(num);
        }
    }
    return duplicates;
}

Объяснение «почему»:

• Сложность: Алгоритм проходит по массиву один раз (O(n)). Каждая операция с HashSet в среднем стоит O(1), что дает общую сложность O(n).
• Компромисс: Мы жертвуем памятью (O(n) для HashSet) ради значительного выигрыша во времени.

Рассмотренные edge-кейсы:

• Пустой или null массив — возвращается пустой список.
• Отрицательные числа и ноль — HashSet корректно с ними работает.
• Очень большие массивы — важно оценить потребление памяти HashSet-ом.

Альтернатива для экономии памяти: Если диапазон чисел ограничен и невелик (например, от 1 до 100), можно использовать boolean-массив, что даст сложность O(n) по времени и O(1) по дополнительной памяти (относительно диапазона).