День 1 — Решение головоломки с двумя суммами

Введение

Приветствую вас с первого дня моей эскапады «100 Days of Code»! В то время как некоторые искатели приключений отправляются на поиски спрятанных сокровищ или запретных секретов, я выбрал печально известную простую задачу с двумя суммами (да, потому что это задача 1 в leetcode). Классическая загадка. Может показаться, что это простая ситуация с выжимкой лимона, но для задачи первого дня это просто правильное сочетание знакомого и загадочного. Итак, товарищи путешественники по коду, будем расшифровывать?

Проблема

Для тех, кто не в курсе, вот краткое изложение (или полный текст). Учитывая массив целых чисел nums и целое число target, верните индексы двух чисел так, чтобы в сумме они составляли target. Звучит просто? Что ж, дьявол кроется в деталях!

Подход грубой силы

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

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Легко, не так ли? Но с большой силой (кодирования) приходит большая ответственность (оптимизация). Это решение не самое эффективное, особенно для больших массивов.

Хеширование спешит на помощь!

Введите: хеш-таблицы (или словари в Python). Они допускают постоянную временную сложность при добавлении и извлечении элементов. Вот более аккуратный подход:

def twoSum(nums, target):
    Targets = {}
    for i in range(len(nums)):
        complement = target - nums[i]
        if complement in Targets:
            return [Targets[complement], i]
        Targets[nums[i]] = i

Сохраняя числа и их индексы по мере выполнения цикла, мы можем мгновенно проверить, существует ли в нашем словаре дополнение к текущему числу (т. е. target - current number).

Анализ сложности решения для хеширования

Сложность времени: предоставленное решение для хеширования проходит по списку чисел только один раз. Это делает его временную сложность O(n), где n — количество элементов в списке. Поскольку мы проверяем и вставляем элементы в словарь за постоянное время, общая временная сложность остается линейной.

Сложность пространства: в худшем случае мы можем хранить каждое число из списка в словаре. Следовательно, пространственная сложность также равна O(n), где n — количество элементов в списке.

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

Заключительные мысли

Задача двух сумм может показаться рудиментарной, но она фундаментальна. Это похоже на кодовую версию обучения приготовлению отличной чашки чая. Вы должны усвоить основы, прежде чем переходить к более причудливым напиткам.

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

Удачного кодирования, искатели приключений! Помните, что каждая строчка кода — это шаг вперед на этом великом пути.