На собеседованиях часто просят написать какой-то простой код. Так компания проверяет, знаете ли вы вообще программирование, и смотрит, как вы работаете с кодом. В новом цикле статей мы разберём популярные вопросы с собеседований и покажем, как их можно решить разными способами.
Задание
У нас есть массив с целыми числами, как с положительными, так и отрицательными. Все числа в массиве разные. Если сложить или вычесть любые два числа из массива, они точно поместятся в стандартной целочисленной переменной.
Ещё у нас есть какое-то целое число — оно не в массиве, а само по себе, отдельной переменной.
Нужно вывести индексы тех двух элементов, которые в сумме дают то самое отдельное число. Например, если в массиве у нас (2, 4, 5, 1, 8), а число — 5, то ответом будет пара 1 и 3, потому что на этих местах стоят числа 4 и 1 (и дают в сумме 5). Помните, что нумерация массивов почти во всех языках программирования начинается с нуля.
Решение простым перебором
Самый простой способ решить эту задачу — перебрать попарно все элементы массива и посмотреть, даст ли какая-то пара нужную сумму. Этот код вряд ли впечатлит работодателя, но результат вы получите верный.
Логика такая:
- В первом цикле перебираем все элементы от первого до предпоследнего.
- Внутрь вкладываем второй, но делаем это так, чтобы не пересекаться по индексам с первым циклом. Для этого смотрим на переменную, с которой работает первый цикл, и начинаем со следующей — и до последнего элемента.
- Внутри второго цикла складываем элементы массива с нашими индексами и смотрим, получился нужный результат или нет.
- Если получился — выводим результат и останавливаемся.
- Если не получился — идём на новый виток цикла.
- Если мы прошли весь массив, но так ничего и не нашли — выводим сообщение о том, что такой пары нет.
# массив с числами
nums = [2, 4, 5, 1, 8]
# сумма
target = 5
# функция, которая найдёт ответ
def twoSum(nums, target):
# сообщение по умолчанию
answer = 'В массиве нет такой пары чисел'
# запускаем первый цикл
for i in range(len(nums) - 1):
# запускаем второй цикл
for j in range(i + 1, len(nums)):
# если получили нужный результат —
if target == nums[i] + nums[j]:
# меняем ответ и добавляем в него индексы элементов
answer = 'Ответ: ' + str(i) + ' и ' + str(j)
# выводим результат работы функции
return answer
# запускаем код
print(twoSum(nums, target))
Решение с дополнительным словарём
Если хотите показать, что вы умеете нестандартно мыслить — используйте приём с дополнительным словарём, в котором данные хранятся попарно: ключ и значение. С ним можно убрать один вложенный цикл и сократить количество вычислений. Работает приём так: мы создаём дополнительный словарь, в котором будем хранить результаты просмотра исходного массива. Но создаём его с одной особенностью: мы будем заполнять его не по порядку, а указывая в качестве ключей значения элементов исходного массива. Например, если в исходном массиве у элемента с индексом 2 значение равно 15, то мы в новом словаре создаём элемент с ключом 15 и кладём туда двойку:
Это даст нам быстрый доступ к индексам уже проверенных элементов — мы просто указываем значение элемента и сразу получаем его индекс в исходном массиве.
Остальная логика выглядит так:
- Перебираем исходный массив и на каждом шаге считаем разницу между нужным значением и очередным элементом.
- Если разница есть в словаре с просмотренными элементами — выводим оба индекса.
- Если разницы в словаре нет — добавляем только что просмотренный элемент в словарь.
Проще говоря, мы перебираем элементы, считаем разницу и смотрим, попадался ли нам результат вычитания среди тех элементов, которые мы уже перебрали. Вот как это выглядит в коде:
# массив с числами
nums = [2, 4, 5, 1, 8]
# сумма
target = 5
# функция, которая найдёт ответ
def twoSum(nums, target):
# сообщение по умолчанию
answer = 'В массиве нет такой пары чисел'
# дополнительный словарь с уже проверенными элементами
hashmap = {}
# перебираем исходный массив
for i in range(len(nums)):
# находим разницу между нужным значением и очередным элементом
complement = target - nums[i]
# если такое значение нам уже попадалось раньше —
if complement in hashmap:
# получаем индекс того значения и выводим ответ
answer = 'Ответ: ' + str(hashmap[complement]) + ' и ' + str(i)
# если не попадалось — запоминаем индекс по значению элемента
hashmap[nums[i]] = i
# выводим результат работы функции
return answer
# запускаем код
print(twoSum(nums, target))
Что дальше
Есть ещё третий способ решения этой задачи — попробуйте найти его сами и почувствовать себя на собеседовании. И подпишитесь, чтобы не пропустить новые статьи с разборами.
