Алгоритм Two Sum в Python
Хеш-таблица позволяет избежать двойного цикла.
Что такое Алгоритм Two Sum в Python?
Хеш-таблица позволяет избежать двойного цикла.
Найдите два значения с заданной суммой.
Когда это использовать?
- Понимать алгоритмы и структуры данных.
- Наблюдать каждый шаг и проверять граничные случаи.
- Сравнивать время работы и память.
Пример кода
main.py
def two_sum(values, target):
seen = {}
for index, value in enumerate(values):
complement = target - value
if complement in seen:
return [seen[complement], index]
seen[value] = index
return []
print(two_sum([2, 7, 11, 15], 9))Ожидаемый результат
[0, 1]Как это работает
Дополнение ищется за O(1): итоговое время O(n), память O(n).
Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.
Практические задания
Изменяйте входные данные и проверяйте граничные случаи перед работой с большими наборами.
- Проверьте пустой ввод, один элемент и дубликаты.
- Выводите состояние после каждого шага.
- Сравните производительность с другим решением.