Эта статья является частью серии статей Натана Томаса, разработчика программного обеспечения полного стека, работающего в Сан-Франциско, Калифорния. Среди других его недавних статей — Создание собственного биткойн-узла и Подмассив максимального продукта.

Введение

Если вы ищете краткое руководство по оптимальному решению проблемы с кодом LeetCode Содержит дубликаты, вы попали по адресу.

Этот вопрос входит в Список вызовов кода для слепых 75 LeetCode — группу вопросов, составленную техническим руководителем Facebook, которая рекламируется как отличный способ подготовиться к собеседованию.

Не корите себя, если вы здесь, потому что вам было тяжело. Мы все учимся в этой отрасли на разных этапах одного и того же пути.

Я не хочу больше тратить ваше время, так что давайте начнем!

Первоначальная настройка 🏗

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

  1. Мы возьмем список из nums
  2. Если какое-либо число встречается в списке дважды, вернуть True логическое значение
  3. Если в списке нет дубликатов, вернуть False

Я буду использовать Python для ответа на этот вопрос, поскольку он немного похож на универсальный язык программирования — предпочитаете ли вы JavaScript, Java, Golang, C или что-то еще, каждый может «отчасти» читать Python.

Я сразу перейду к делу и дам вам «оптимальный» способ решения проблемы (хотя я буду писать так, чтобы его намеренно было просто понять). Мы не будем тратить время на разговоры о неэффективных решениях.

Вы пришли сюда за ответом, верно? Ты собираешься получить хороший.

Итак… Давайте приступим к делу.

Создание наших переменных и цикла 🪣

Первое, что мы можем сделать, это написать переменную прямо внутри нашей функции, которая позволит нам отслеживать числа, которые мы уже видели (например, ведро).

Мы можем сделать это, инициализировав словарь:

Следующее, что нам нужно сделать, это построить цикл for, который позволит нам перебирать список nums.

Этого достаточно, чтобы начать писать нашу условную логику. Мы будем использовать оператор if / else здесь, чтобы условно выполнить некоторую логику.

Оглянемся назад 👀

Хотя мы могли бы решить эту проблему, просто написав еще один вложенный цикл for, это в конечном итоге дало бы нам временную сложность O(n^2). Мы можем сделать лучше, чем это!

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

Для каждого номера мы можем проверить, существует ли он уже в tracker. Если это так, мы можем вернуть True (поскольку список содержит дубликаты).

Если мы не найдем номер в нашем tracker, мы можем настроить его на отслеживание позже. Вот как это выглядит в виде кода:

Мы проверяем, находится ли num в tracker, и возвращаем True, если да. Если нет, мы сохраняем этот номер, чтобы ссылаться на него позже.

Если мы пройдем весь список nums, не возвращая True, это означает, что дубликатов нет. Чтобы справиться с этим, мы можем просто иметь оператор return False в конце функции для обработки всех случаев, когда нет дубликатов (или даже если список пуст).

Вот как выглядит решение задачи кодирования:

Это решение будет работать с временной сложностью O(n) (для повторения всего списка nums) и пространственной сложностью O(n) (для хранения каждого числа в tracker).

Заключение

Поздравляю! 🎉 Вы решили проблему.

Я также надеюсь, что вы узнали что-то такое же, как мне понравилось писать это.

Следите за остальными статьями Слепые 75 проблем с программированием. Это будет веселая поездка.

Кроме того, не стесняйтесь обращаться ко мне по любой из приведенных ниже ссылок, если вы хотите поговорить о кодировании, крутых технологиях или о чем-то еще (я люблю рекомендации хороших книг).

Спасибо за прочтение. 🔥

Натан

(GitHub, LinkedIn, Twitter и Персональный сайт)