1. Сумма двух(Two Sum)

👨‍💻 Задача:
Учитывая массив целых чисел nums и целое число target, верните индексы двух чисел, сумма которых равна target. Вы можете предположить, что для каждого ввода будет ровно одно решение, и вы не можете использовать один и тот же элемент дважды.Вы можете вернуть ответ в любом порядке.

Продолжение: можете ли вы придумать алгоритм, который будет работать быстрее O(n2) временная сложность?

📊 Пример:

Ввод: nums = [2,7,11,15], target = 9
Вывод: [0,1]
Пояснение: Поскольку nums[0] + nums[1] == 9, мы возвращаем [0, 1].

⚡ Решение:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_map = {}
        for i in range(len(nums)):
            hash_map[nums[i]] = i
        for i in range(len(nums)):
            missing_element = target - nums[i]
            if missing_element in hash_map and hash_map[missing_element] != i:
                return [i, hash_map[missing_element]]
        return []

🧠 Алгоритм решения:
Мы решаем эту задачу с помощью двухпроходной хэш-таблицы. Почему двух? 🤔 Потому что проходимся циклом for дважды!

1. На первой итерации добавляем значение каждого элемента в качестве ключа и его индекс в качестве значения в хэш-таблицу (ключ — значение элемента, значение — индекс этого элемента).

2. На второй итерации проверяем, существует ли дополнение каждого элемента (target - nums[i]) в хэш-таблице. Если оно существует, возвращаем индекс текущего элемента и индекс его дополнения.

🔍 Важно: Дополнение не должно совпадать с nums[i]!

🔥 15 - и я пойму, что стоит решать и делать такой контент дальше!

#leetcode