Поиск дубликатов в массиве

Поиск дубликатов в массиве

Это классическая задача на собеседованиях, проверяющая понимание структур данных и сложности алгоритмов. Рассмотрим несколько подходов с разной эффективностью.

Решение 1: HashSet (оптимальное) — O(n) время, O(n) память

Самое быстрое и популярное решение — использовать HashSet, который проверяет наличие элемента за O(1):

public class DuplicateFinder {
    public static boolean containsDuplicate(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }
        
        HashSet<Integer> seen = new HashSet<>();
        
        for (int num : nums) {
            if (seen.contains(num)) {
                return true;
            }
            seen.add(num);
        }
        
        return false;
    }
    
    public static void main(String[] args) {
        System.out.println(containsDuplicate(new int[]{1, 2, 3, 1}));
        System.out.println(containsDuplicate(new int[]{1, 2, 3, 4}));
        System.out.println(containsDuplicate(new int[]{}));
        System.out.println(containsDuplicate(new int[]{5}));
    }
}

Как это работает:

1. Проходим по каждому элементу массива
2. Для каждого элемента проверяем, есть ли он уже в HashSet
3. Если есть — возвращаем true (найден дубликат)
4. Если нет — добавляем элемент в set и продолжаем
5. Если прошли весь массив — возвращаем false

Решение 2: Сортировка — O(n log n) время

Альтернативный подход — отсортировать массив и сравнивать соседние элементы:

public class DuplicateFinderSorted {
    public static boolean containsDuplicate(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }
        
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        
        return false;
    }
}

Как это работает:

1. Сортируем массив (O(n log n))
2. Проходим по отсортированному массиву
3. Если нашли два одинаковых соседних элемента — возвращаем true
4. Иначе — false

Решение 3: Stream API (современный подход)

В Java 8+ можно использовать Stream API:

public class DuplicateFinderStream {
    public static boolean containsDuplicate(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }
        
        return Arrays.stream(nums)
                .boxed()
                .collect(Collectors.toSet())
                .size() < nums.length;
    }
}

Решение 4: Оптимизированное

public class OptimizedDuplicateFinder {
    public static boolean containsDuplicate(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }
        
        Set<Integer> seen = new HashSet<>(nums.length);
        for (int num : nums) {
            if (!seen.add(num)) {
                return true;
            }
        }
        return false;
    }
}

Эта версия немного эффективнее, так как add() выполняет и проверку, и добавление одновременно.

Сравнение подходов

Выводы

1. На собеседовании предложите решение с HashSet — лучший компромисс
2. Будьте готовы объяснить альтернативные подходы
3. Учитывайте граничные случаи — пустой массив, один элемент, null
4. Думайте о памяти — иногда сортировка может быть предпочтительнее
5. Знайте сложность — O(n) vs O(n log n) важна при больших данных