Пересечение двух слайсов

Решение

Задача требует найти элементы, которые присутствуют одновременно в обоих слайсах. Ключевой момент — входные данные неупорядочены, поэтому прямое сравнение неэффективно.

Подход

Используем map (хеш-таблицу) для оптимизации:

1. Создаём map из элементов первого слайса
2. Итерируем по второму слайсу и ищем совпадения
3. Добавляем найденные элементы в результат (учитывая дубликаты)

Реализация

func intersection(a, b []int) []int {
    // Создаём map для быстрого поиска элементов первого слайса
    // Ключ — число, значение — количество вхождений
    mapA := make(map[int]int)
    for _, num := range a {
        mapA[num]++
    }
    
    var result []int
    
    // Итерируем по второму слайсу
    for _, num := range b {
        // Если элемент есть в первом слайсе и его count > 0
        if count, exists := mapA[num]; exists && count > 0 {
            result = append(result, num)
            mapA[num]--  // Уменьшаем count, чтобы не добавить дубликат
        }
    }
    
    return result
}

Анализ сложности

• Временная сложность: O(n + m), где n и m — длины слайсов. Одна итерация по a, одна по b, поиск в map — O(1).
• Пространственная сложность: O(min(n, m)) — размер map и результата.

Пример работы

Вход: a = {1, 2, 3, 4, 5}, b = {4, 5, 6, 7, 8}

1. Создаём map из a: {1:1, 2:1, 3:1, 4:1, 5:1}
2. Итерируем по b:
   - 4 → есть в map (count=1) → добавляем в result, count становится 0
   - 5 → есть в map (count=1) → добавляем в result, count становится 0
   - 6, 7, 8 → нет в map
3. Результат: {4, 5}

Альтернативный подход (для упорядоченных слайсов)

Если бы слайсы были отсортированы, можно было бы использовать two-pointers с O(n + m) временем и O(1) доп. памятью:

func intersectionSorted(a, b []int) []int {
    var result []int
    i, j := 0, 0
    
    for i < len(a) && j < len(b) {
        if a[i] < b[j] {
            i++
        } else if a[i] > b[j] {
            j++
        } else {
            result = append(result, a[i])
            i++
            j++
        }
    }
    
    return result
}

Но для неупорядоченных данных первый подход с map — оптимален и практичен.