Проблема
Учитывая массив целых чисел, возвращайте индексы двух чисел, чтобы они в сумме давали определенную цель.
Вы можете предположить, что каждый вход будет иметь ровно одно решение.
Ссылка: https://leetcode.com/problems/two-sum/
Объяснение решения
В моей голове два решения. Первый — более простой способ решить эту проблему. Использование вложенного цикла для просмотра каждой комбинации элементов и проверки результата суммы, если он равен цели. Но это не эффективный способ. Временная сложность — O(N²).
Во втором решении мы можем использовать карту для хранения местоположения элемента во входном массиве. В следующей программе, если map[difference] не пусто, это означает, что цель может быть добавлена по значению differenceand. Просто верните местоположение разницы и значения, вот и ответ. Временная сложность решения2 составляет O (N).
Время выполнения решения 1 составляет 948 мс, а второго — 82 мс. Увеличиваем производительность в 11 раз!
Тестовые случаи
Временная сложность решения
O(N)