Сложность: 🟢 Легкая
ℹ️ Описание
Дан массив целых чисел nums.
Напишите функцию twoSum, которая будет находить в массиве два числа, сумма которых равна определенному целевому
числу target.
В качестве результата функция должна возвращать массив с индексами элементов, удовлетворяющих условию.
Порядок индексов в ответе не важен.
⚠️ Ограничения
🔹 В массиве может быть от 2 до 10^4 уникальных значений
🔹В качестве значений могут быть числа в диапазоне от -10^9 до 10^9
🔹Значение
target может быть в диапазоне от -10^9 до 10^9🔹Для массива всегда есть только одно решение
1️⃣ Пример
Вход:
nums = [2, 7, 11, 15]
target = 9
Ответ: [0, 1] или [1, 0]
Сумма 2 и 7 равна 9. Следовательно, index1 = 0, index2 = 1.
Возвращаем [0, 1].
2️⃣ Пример
Вход:
nums = [-1, 0]
target = -1
Ответ: [0, 1] или [1, 0]
Сумма -1 и 0 равна -1. Следовательно, index1 = 0, index2 = 1.
Возвращаем [0, 1].
✅ Решение
Для того, чтобы эффективно решить эту задачу, надо придумать как получать индекс числа из массива не перебирая его.
В этом нам может помочь структура Map (или ее аналоги), которая позволяет получать значение по ключу за константное время.
Изначально мы инициализируем пустую мапу, в которцю будем записывать в качестве ключа число, а в качестве значения — его индекс в массиве.
Далее запускаем цикл по всем элементам массива, в котором выполняем следующие проверки на каждой итерации.
1. Высчитываем разницу между target и текущим числом из массива. Это второе искомое число, которое нам нужно.
2. Чтобы проверить, есть ли число в массиве, мы обращаемся в нашу мапу с текущим числом в качестве ключа.
Если в мапе есть такое число, значит мы его уже ранее добавляли из массива и можем получить его индекс.
Мы нашли искомую пару чисел и можем вернуть их индексы в виде массива в качестве ответа.
3. Если в мапе нет такого числа, значит нужно его туда добавить. В качестве ключа используем само число, а в качестве значения его индекс.
Посмотреть реализацию
🅾️ Оценка сложности
n - количество элементов в массиве
Сложность по времени O(n), так как мы итерируемся по всем элементам массива.
Сложность по памяти O(n), так как мы добавляем в мапу n элементов.
#easy #arrays