Продолжаю решать задачи на LeetCode для тренировки мозга и создания новых нейронных связей! Сегодня передо мной стоит задача из разряда легких под названием Two Sum.
Условия задачи
На вход функции передается список целых чисел (nums) и одно целое число (target). Необходимо вернуть список, состоящий из индексов двух чисел из списка nums. При этом сумма этих чисел должна быть равна target.
Примеры входных данных
Получив на вход список nums = [2, 7, 11, 15] и target = 9, функция должна вернуть следующий список: [0, 1], так как сумма элементов с индексами 0 и 1 (это 2 и 7 в списке nums соответственно) равна 9.
Начинаю рассуждения
В первую очередь я должен найти самый простой случай и обработать его. Функция на вход может получить список, состоящий всего из двух элементов. При этом сумма этих элементов как раз равна target. Например, мы получаем список [2, 4] и target равный 6, то функция должна вернуть список [0, 1]. Здесь все логично.
Подзадача поставлена, пора ее решать.
Код для самого простого случая
Чтобы отловить входящий список равный двум, нужно измерить его длину функцией len() и присвоить ее переменной length_nums, вдруг еще пригодится.
Собственно далее нужно сделать две проверки:
- равна ли длина списка двум;
- равна ли сумма элементов списка заданному числу target.
Чтобы не получать каждый элемент по его индексу и потом складывать, думаю использовать функцию sum(), передав в качестве аргумента список. В итоге получается следующий блок кода:
length_nums = len(nums)
if length_nums == 2 and nums[0] + nums[1] == target:
return [0, 1]
Проверяю. На вход функция получает следующие данные:
nums = [2, 4] target = 6
Функция возвращает:
[0, 1]
Если изменить target, например, на 7, чтобы проверить негативный сценарий, то функция ничего не вернет, точнее вернет None, так как я пока не обрабатываю вариант, если условие не срабатывает.
Продолжаю рассуждать
Теперь вернусь к входным данным, которые приведены в качестве примера при описании условий задачи.
nums = [2, 7, 11, 15] target = 9
Раз есть список, значит можно по нему пробежаться, например, циклом for, как по элементам, так и по индексам. Я буду «бежать» по индексам. Для этого мне понадобиться встроенная функция range().
Точнее range() не совсем функция. Согласно документации range is actually an immutable sequence type (неизменяемая последовательность).
Используемые параметры: start, stop, step.
На первом шаге пройдемся по индексам от первого до предпоследнего. Как известно, индексация элементов в итерируемых объектах начинается с 0. Для этого, в качестве параметра функции range() передаю длину списка nums. Но если оставить в таком виде, при длине списка, равной 4, последним значением последовательности будет число 3, а это индекс последнего элемента списка nums. Такое поведение мне не подойдет. Поэтому при указании параметра stop из длины списка nums я вычту единицу. В таком случае, при указанной длине списка последним элементом последовательности будет число 2, что соответствует индексу предпоследнего элемента списка.
for left_index in range(length_nums):
pass
Таким образом, на каждой итерации цикла for переменная left_index будет последовательно получать ссылку на элемент сгенерированной последовательности. То есть, на первой итерации мы получим индекс, равный 0, на второй — равный 1 и т. д.
Но для решения поставленной задачи этого, как мне кажется, мало. Мне нужно сравнить сумму двух элементов в списке с заданным числом. Один элемент у меня есть, надо получить и второй.
Собственно ничего другого я не смог придумать, кроме того как вложить в цикл for еще один for. Отличие лишь в том, что в этот раз я задам два параметра функции range(). В качестве параметра start будет выступать индекс второго элемента, который равен индексу первого элемента, увеличенного на единицу. В качестве параметра stop я задам длину списка nums.
Как итог работы этих двух циклов, я последовательно смогу сравнить суммы всех возможных пар элементов в списке с заданным значением. Как только условие будет выполнено, функция вернет список с индексами двух элементов, сумма которых равна заданному числу target.
Результаты работы кода
Все тесты на платформе LeetCode проходят. Да, решение мое не самое эффективное, есть к чему стремиться! Возможно, что в этой задаче можно было бы применить рекурсию, но она мне пока так просто не дается! Но ничего, одну из следующих задач обязательно возьму на рекурсию.
- Runtime – 1689 ms — обгоняет 33.33% пользователей Python
- Memory – 18.19 mb — обгоняет 31.73% пользователей Python
Полный код решения задачи
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
length_nums = len(nums)
if length_nums == 2 and nums[0] + nums[1] == target:
return [0, 1]
for left_index in range(length_nums):
for right_index in range(left_index + 1, length_nums):
if nums[left_index] + nums[right_index] == target:
return [left_index, right_index]