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

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

Вы можете предположить, что для каждого ввода будет ровно одно решение, и вы не можете использовать один и тот же элемент дважды ».

Вот мое решение:

У меня была возможность обсудить эту проблему с другом, и он сказал мне, что есть несколько способов решения этой проблемы, и мое решение на самом деле является одним из худших сценариев. Мое решение обеспечивает время выполнения O (n²). Позвольте мне рассмотреть некоторые из возможных решений.

РЕШЕНИЕ BRUTE FORCE:

Мое решение - это так называемый перебор грубой силы. Грубая сила проверяет каждый возможный элемент и проверяет, соответствует ли он критериям. Идея использования грубой силы в производстве ужасна, потому что, если у вас есть 1 миллион учетных записей, и вам нужно проверить все 1 миллион, чтобы узнать, есть ли у вас 1 пользователь, это непрактично. Есть много случаев, когда грубая сила является приемлемым решением, если набор данных невелик, но когда набор данных значительный, тогда решение грубой силы не будет приемлемым. Представьте, что в массиве более 1 миллиона индексов. Временная сложность O (n²).

ХЭШ-ТАБЛИЦА:

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

Время выполнения этого в LeetCode составляет 56 мс по сравнению с методом грубой силы 126 мс. Большой O хеш-решения - O (n). В первом цикле мы используем хеш-поиск, который в среднем составляет O (1), а затем мы просматриваем каждый элемент, чтобы увидеть, можем ли мы найти существующий ключ для разницы текущего элемента.

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