Задача Two Sum требует найти индексы двух различных чисел в списке, которые в сумме дают заданное целевое значение. Оптимальное решение использует хэш-мапу для достижения временной сложности O(n).
Вместо проверки каждой пары чисел (что было бы O(n²)), мы используем словарь под названием seen, чтобы сохранять каждое число и его индекс по мере итерации. Для каждого элемента мы вычисляем его дополнение — значение, необходимое для достижения целевого числа — и проверяем, существует ли оно уже в словаре.
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
seen хранит каждое число как ключ и его индекс как значениеcomplement = target - numseen, мы нашли пару — возвращаем оба индексаseenO(n) — один проход по спискуO(n) — хэш-мапа хранит до n элементовСохраняя ранее просмотренные числа в хэш-мапе, каждый поиск выполняется за O(1), что делает этот подход значительно более эффективным, чем наивный подход с вложенными циклами. Алгоритм гарантирует наличие результата, согласно условию задачи.
Алгоритм two sum достигает временной сложности O(1), используя hash map для хранения ранее встреченных чисел и их индексов.
Новый — ещё не проверен сообществом
Вы