Пример решения задачи #1 на Python LeetCode — Сумма двух

Вариант решения задачи на языке программирования Python с LeetCode.
Категория: Алгоритмы.
Название задачи: Сумма двух (Two Sum).
Сложность: Легкая.
Статус решения: "Решено".

Условие задачи:
Учитывая массив целых чисел nums и целочисленную цель, верните индексы двух чисел так, чтобы их сумма составляла целевое значение.

Решение:

Python


class Solution(object):
    def twoSum(self, nums, target):
        """
        Находит индексы двух чисел в массиве, сумма которых равна целевому значению.

        Args:
            nums: Список целых чисел.
            target: Целевое значение суммы.

        Returns:
            Список из двух индексов, если решение найдено.
            Пустой список, если решение не найдено.
        """

        # Создаем словарь для хранения уже встречавшихся чисел и их индексов.
        seen = {}
        for i, num in enumerate(nums):
            # Вычисляем число, которое нужно добавить к текущему, чтобы получить целевое значение.
            complement = target - num

            # Проверяем, есть ли уже такое число в словаре.
            if complement in seen:
                # Если есть, возвращаем индексы найденных чисел.
                return [seen[complement], i]

            # Добавляем текущее число и его индекс в словарь.
            seen[num] = i

        # Если решение не найдено после проверки всех чисел, возвращаем пустой список.
        return []

Объяснение кода

Класс Solution и метод twoSum

class Solution(object): Определяет класс Solution, который будет содержать нашу функцию для решения задачи.
def twoSum(self, nums, target): Определяет метод twoSum внутри класса Solution. Этот метод принимает на вход:
nums: список целых чисел, в котором мы будем искать нужные элементы.
target: целевое значение, сумму которого мы хотим найти.

Создание словаря seen
seen = {}: Создается пустой словарь seen. Этот словарь будет использоваться для хранения информации о том, какие числа мы уже встречали и на каких индексах они находятся.

Цикл по массиву nums
for i, num in enumerate(nums): Начинается цикл, который проходит по каждому элементу списка nums. Переменная i будет хранить индекс текущего элемента, а num будет хранить само значение элемента.

Вычисление комплемента
complement = target - num: Вычисляется значение complement, которое нужно добавить к текущему числу num, чтобы получить целевое значение target. Например, если target равен 9, а текущее число num равно 7, то complement будет равен 2.

Проверка наличия комплемента в словаре
if complement in seen: Проверяется, есть ли уже вычисленное значение complement в словаре seen. Если такое значение есть, значит мы нашли два числа в массиве, сумма которых равна target.

Возврат индексов
return [seen[complement], i]: Если complement найден в словаре, то возвращается список из двух индексов:
seen[complement] - индекс числа, которое мы нашли в словаре и которое является комплементом текущего числа.
i - индекс текущего числа.

Добавление числа в словарь
seen[num] = i: Если complement не найден в словаре, то текущее число num и его индекс i добавляются в словарь seen. Это делается для того, чтобы при последующих итерациях цикла мы могли быстро проверить, встречалось ли уже такое число.

Возврат пустого списка
return []: Если цикл завершился, а решение так и не было найдено, то возвращается пустой список, что означает, что в массиве нет двух чисел, сумма которых равна target.

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

Быстрый поиск: Проверка на наличие числа в словаре происходит за постоянное время, что делает алгоритм эффективным.
Экономия памяти: Словарь хранит только уникальные значения и их индексы.
Этот алгоритм позволяет найти два числа в массиве, сумма которых равна заданному значению, за один проход по массиву, что делает его очень эффективным.

Источник решения: hdhai.com