Решите Two Sum за O(n), вернув два индекса
Реализуйте twoSum(nums, target), возвращающую индексы двух чисел, дающих в сумме target. Требования: O(n) по времени — один проход, а не перебор O(n²) вложенным циклом. Верните исходные индексы (не сортируйте, теряя их). Считайте, что валидная пара ровно одна.
func twoSum(nums []int, target int) []int {
// ваш код здесь
return nil
}Допишите реализацию.
Держите map[int]int из значения в индекс. Итерируйте for i, n := range nums; для каждого n ищите target-n через comma-ok — если найдено по индексу j, верните []int{j, i}, иначе сохраните seen[n] = i. Это O(n) против перебора O(n²) вложенным циклом.
- ✗Сортировать сначала и терять исходные индексы, которые требует задача
- ✗Делать два прохода, когда хватает одного с comma-ok
- ✗Считать перебор вложенным циклом O(n) в среднем
- →Почему хранение значение→индекс позволяет найти дополнение за один проход?
- →Как обработать дубликаты, образующие пару, например
[3,3]с target 6?
Задача
Вернуть индексы двух чисел, дающих в сумме target.
func twoSum(nums []int, target int) []int {
seen := make(map[int]int) // значение -> индекс
for i, n := range nums {
if j, ok := seen[target-n]; ok {
return []int{j, i}
}
seen[n] = i
}
return nil
}Как это работает
Идея — за один проход помнить уже виденные числа в map[int]int (значение → индекс).
Для каждого n нужное «дополнение» — это target - n. Если оно уже встречалось (j, ok := seen[target-n] с паттерном comma-ok), пара найдена: возвращаем []int{j, i}. Иначе записываем seen[n] = i и идём дальше.
Каждый элемент обрабатывается один раз с O(1)-поиском в map, поэтому общая сложность — O(n) против O(n²) у наивного двойного цикла.
⚠️ Демонстрирует идиоматичный comma-ok и хеш-таблицу вместо перебора.
