PrepBro
← Назад к вопросам

Two Sum

2.0 Middle🔥 181 комментариев
#Основы Go

Условие

Дан массив целых чисел nums и целое число target. Верните индексы двух чисел, сумма которых равна target.

Можно предположить, что каждый вход имеет ровно одно решение, и вы не можете использовать один и тот же элемент дважды.

Сигнатура

func twoSum(nums []int, target int) []int

Примеры

Вход: nums = []int{2, 7, 11, 15}, target = 9 Выход: []int{0, 1} (потому что nums[0] + nums[1] = 2 + 7 = 9)

Вход: nums = []int{3, 2, 4}, target = 6 Выход: []int{1, 2}

Дополнительно

Постарайтесь решить за O(n) по времени, используя хеш-таблицу.

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение Two Sum

Описание задачи

Задача требует найти два индекса элементов массива, сумма которых равна целевому значению. Ограничения: каждый элемент можно использовать только один раз, и решение существует всегда.

Подход с хеш-таблицей (O(n) по времени)

Оптимальное решение использует хеш-таблицу (map в Go) для хранения пройденных чисел и их индексов. Идея простая:

  1. Проходим по массиву один раз
  2. Для каждого элемента проверяем, есть ли уже в map число, которое дополнит текущий элемент до target
  3. Если есть — возвращаем индексы
  4. Если нет — добавляем текущее число в map и продолжаем

Время: O(n) — один проход по массиву. Пространство: O(n) — размер map в худшем случае.

Реализация

func twoSum(nums []int, target int) []int {
    seen := make(map[int]int)
    for i, num := range nums {
        complement := target - num
        if j, exists := seen[complement]; exists {
            return []int{j, i}
        }
        seen[num] = i
    }
    return []int{}
}

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

Дан массив nums = [2, 7, 11, 15], target = 9:

  • i=0, num=2: complement = 7. В map пусто. Добавляем: {2: 0}
  • i=1, num=7: complement = 2. В map есть 2 → индекс 0! Возвращаем [0, 1]

Дан массив nums = [3, 2, 4], target = 6:

  • i=0, num=3: complement = 3. В map пусто. Добавляем: {3: 0}
  • i=1, num=2: complement = 4. В map пусто. Добавляем: {3: 0, 2: 1}
  • i=2, num=4: complement = 2. В map есть 2 → индекс 1! Возвращаем [1, 2]

Ключевые моменты

  • Map в Go: быстрый поиск O(1) в среднем
  • Однопроходной алгоритм: экономит память и время
  • Порядок индексов: первый индекс меньше второго (автоматически)
  • Сложность: Time O(n), Space O(n)

Это классическая задача, часто встречается в интервью.

Two Sum | PrepBro