Задача «Две суммы» — это вводная алгоритмическая задача, с которой вы можете столкнуться на собеседованиях. Это удобная для новичков задача, имеющая несколько распространенных решений, хотя и не все они одинаковы. Давайте посмотрим на два из них.

Задача заключается в следующем: «Дано массив целых чисел nums и целое число target, вернуть индексы двух чисел так, чтобы в сумме они составляли target. Вы можете предположить, что каждый вход будет иметь ровно одно решение, и вы не можете использовать один и тот же элемент дважды. Вы можете вернуть ответ в любом порядке». Например:

числа = [2, 5, 4, 1, 7]

цель = 3

цель = [0, 3]

Решение 1: грубая сила

Это решение содержит вложенный цикл for, что, конечно же, приводит к временной сложности O(n²). Это означает, что для каждого элемента в массиве мы проверяем сумму этого элемента с каждым другим элементом. Если мы находим решение, мы помещаем два числа в массив, а затем продолжаем проверку. Это означает, что если мы найдем решение с первым пробуемым набором чисел, цикл на этом не остановится, каждая последующая пара все равно будет суммироваться и проверяться. Мы могли бы немного улучшить время вычислений, если бы вышли из цикла, как только решение будет найдено — поскольку проблема LeetCode позволяет нам предположить только одно решение для каждого массива. Хотя это улучшение, это все же нежелательное решение O(n²).

Решение 2. Воспользуемся хэш-картой

Давайте посмотрим, что происходит в этом фрагменте. Во-первых, мы создаем пустой объект, который будет использоваться в качестве нашей хеш-карты. Затем мы проходим по массиву nums и проверяем, находится ли дополнение(т. е. целевое число) числа в хэш-карте. Если это правда, мы возвращаем массив с индексом дополнения и индексом текущего числа. Если это утверждение неверно, мы добавляем текущий номер в качестве ключа с его индексом в качестве значения. Эта структура данных, называемая хэш-картой, позволяет нам найти решение, проходя по массиву только один раз. Этот метод дает нам O(n)сложность по времени, которую мы ищем в решении.

Я надеюсь, что эти решения были полезными, и я призываю вас подписаться и ознакомиться с другими моими решениями!