Grind 75. Two Sum (1/75)

Grind 75 - это набор из 75 задач по алгоритмам и структурам данных, которые рекомендуется решать для подготовки к техническим интервью в IT-компаниях. Эти задачи были собраны сообществом разработчиков и являются одним из наиболее популярных наборов задач для подготовки к техническим интервью.

Каждая статья будет посвящена решению одной задачи, которую мы будем разбирать на конкретных примерах и давать подробные объяснения каждого шага. Мы также будем обсуждать эффективность каждого алгоритма и его сложность.

В этой статье мы начнем с первой задачи TwoSum. Для начала попробуйте ее решить самостоятельно.

На вход подается 2 параметра:

1) nums - массив целых чисел

2) target - искомое целое число

Необходимо вернуть новый массив из 2-ух индексов массива nums, сумма чисел которых будет равняться искомому числу target.

Примеры:

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

Пример 2:
Параметры: nums = [3,2,4], target = 6
Результат: [1,2]

Пример 3:
Параметры: nums = [3,3], target = 6
Результат: [0,1]

Для решения данной задачи, мы используем два вложенных цикла. Внешний цикл перебирает все элементы массива nums, а внутренний цикл перебирает все оставшиеся элементы после i-го элемента. Таким образом, мы проверяем все возможные комбинации чисел в массиве.

Объявим функцию twoSum и запишем два цикла внутри нее:

Прошу заметить, что j равняется i + 1, это было сделано для того, чтобы мы не брали в расчет элементы, которые остались слева от элемента i, потому что тогда мы будем проверять уже рассмотренные комбинации чисел, что не имеет смысла и может привести к повторным результатам.

Теперь осталось проверить, что сумма чисел i и j будет равняться числу target, если это так, то мы вернем индексы этих элементов [i, j]:

Ответ принят, но скорость выполнения оставляет желать лучшего, попробуем оптимизировать наше решение.

Давайте попробуем избавиться от внутреннего цикла и используем хэш-таблицу для записи и быстрого доступа к элементам, что заметно даст нам прирост к эффективности выполнения программы.

Алгоритм заключается в следующем:

1. Создаем пустой объект hash.

2. Проходим по всем элементам массива nums с помощью цикла for.

3. Для каждого элемента nums[i] вычисляем число, которое нам нужно для сложения с элементом nums[i], чтобы получить target, sub = target - nums[i].

Например: искомое число 10, элемент равен 7, следовательно sub = 3. В следующем шаге мы произведем проверку наличия sub в hash.

4. Проверяем, есть ли значение sub в объекте hash. Если есть, значит мы нашли два числа, которые в сумме дают target, и возвращаем массив с индексами этих чисел [i, hash[sub]].

5. Если значение sub не найдено в объекте hash, то добавляем текущий элемент nums[i] и его индекс i в объект hash.

Теперь осталось написать алгоритм:

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

Благодаря использованию хэш-таблицы, мы заметно ускорили наш алгоритм решения.

Поздравляю, вы решили первую задачу из Grind 75.

Подписывайтесь на канал, чтобы не пропустить разбор следующих задач. Будем двигаться вместе на пути к улучшению своих навыков:)