Разбор: задача про массив и сумму чисел

Разбор: задача про массив и сумму чисел

Простой код для собеседований

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

Задание

У нас есть массив с целыми числами, как с положительными, так и отрицательными. Все числа в массиве разные. Если сложить или вычесть любые два числа из массива, они точно поместятся в стандартной целочисленной переменной.

Ещё у нас есть какое-то целое число — оно не в массиве, а само по себе, отдельной переменной.

Нужно вывести индексы тех двух элементов, которые в сумме дают то самое отдельное число. Например, если в массиве у нас (2, 4, 5, 1, 8), а число — 5, то ответом будет пара 1 и 3, потому что на этих местах стоят числа 4 и 1 (и дают в сумме 5). Помните, что нумерация массивов почти во всех языках программирования начинается с нуля.

Решение простым перебором

Самый простой способ решить эту задачу — перебрать попарно все элементы массива и посмотреть, даст ли какая-то пара нужную сумму. Этот код вряд ли впечатлит работодателя, но результат вы получите верный.

Логика такая:

  1. В первом цикле перебираем все элементы от первого до предпоследнего.
  2. Внутрь вкладываем второй, но делаем это так, чтобы не пересекаться по индексам с первым циклом. Для этого смотрим на переменную, с которой работает первый цикл, и начинаем со следующей — и до последнего элемента.
  3. Внутри второго цикла складываем элементы массива с нашими индексами и смотрим, получился нужный результат или нет.
  4. Если получился — выводим результат и останавливаемся.
  5. Если не получился — идём на новый виток цикла.
  6. Если мы прошли весь массив, но так ничего и не нашли — выводим сообщение о том, что такой пары нет.

# массив с числами
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 и кладём туда двойку:

Разбор: задача про массив и сумму чисел

Это даст нам быстрый доступ к индексам уже проверенных элементов — мы просто указываем значение элемента и сразу получаем его индекс в исходном массиве. 

Остальная логика выглядит так:

  1. Перебираем исходный массив и на каждом шаге считаем разницу между нужным значением и очередным элементом.
  2. Если разница есть в словаре с просмотренными элементами — выводим оба индекса.
  3. Если разницы в словаре нет — добавляем только что просмотренный элемент в словарь.

Проще говоря, мы перебираем элементы, считаем разницу и смотрим, попадался ли нам результат вычитания среди тех элементов, которые мы уже перебрали. Вот как это выглядит в коде:

# массив с числами
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))
Разбор: задача про массив и сумму чисел

Что дальше

Есть ещё третий способ решения этой задачи — попробуйте найти его сами и почувствовать себя на собеседовании. И подпишитесь, чтобы не пропустить новые статьи с разборами.

Код:

LeetCode

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Художник:

Алексей Сухов

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев

Соцсети:

Виталий Вебер

Любишь Python? Зарабатывай на нём!
Изучите самый модный язык программирования и станьте крутым бэкенд-разработчиком. Старт — бесплатно.
Попробовать
Любишь Python? Зарабатывай на нём! Любишь Python? Зарабатывай на нём! Любишь Python? Зарабатывай на нём! Любишь Python? Зарабатывай на нём!
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
easy