Проблема

Учитывая массив целых чисел, возвращайте индексы двух чисел, чтобы они в сумме давали определенную цель.

Вы можете предположить, что каждый вход будет иметь ровно одно решение.

Ссылка: https://leetcode.com/problems/two-sum/

Объяснение решения

В моей голове два решения. Первый — более простой способ решить эту проблему. Использование вложенного цикла для просмотра каждой комбинации элементов и проверки результата суммы, если он равен цели. Но это не эффективный способ. Временная сложность — O(N²).

Во втором решении мы можем использовать карту для хранения местоположения элемента во входном массиве. В следующей программе, если map[difference] не пусто, это означает, что цель может быть добавлена ​​по значению differenceand. Просто верните местоположение разницы и значения, вот и ответ. Временная сложность решения2 составляет O (N).

Время выполнения решения 1 составляет 948 мс, а второго — 82 мс. Увеличиваем производительность в 11 раз!

Тестовые случаи

Временная сложность решения

O(N)