Сумма трех чисел в массиве. Решение без предварительной сортировки

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

Необходимо также проитерироваться по всем элементам массива и на каждой итерации запустить отдельный цикл от i + 1. Для того чтобы не проверять повторяющиеся числа, мы будем записывать каждое в структуру Hash Set dups и в начале итерации проверять, если уже такой элемент. Если в Hash Set уже есть такое число, то мы просто пропускаем итерацию.

Также необходимо определить Hash Map seen, в которую мы будем записывать уже проверенные пары двоек firstNum и secondNum. При таком подходе мы можем вычислять на каждой итерации второго цикла недостающее число thirdNum и проверять есть ли уже такая пара в seen. Если такая пара есть, то мы нашли искомую тройку.

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

В таких языках, как Python и Java мы можем создать массив (лист) из трех элементов, отсортировать их в любом порядке и добавить в еще один Has Set uniq. Добавление отсортированных троек обеспечит автоматическое избавление от дублей благодаря механике Hash Set. В конце просто нужно конвертировать Hash Set в массив и вернуть в качестве ответа.

Однако, в таких языках как, например, Go, JavaScript и TypeScript провернуть такое не получится. В Go нельзя использовать слайсы в качестве ключей, потому что это не сравниваемые типы. В JavaScript и TypeScript массивы использовать можно, но они передаются по ссылке, поэтому в Hash Set можно спокойно добавить одинаковые массивы, так как у них разные ссылки.

В этих языках в качестве ключа придется использовать строку вида «1.2.3», где через точку записаны три числа из тройки в отсортированном порядке. Таким образом мы создадим уникальный ключ и избежим дубликатов при добавлении. Однако, при возврате результата нам придется обратно разобрать каждую строку на отдельные числа с приведением типов.

Посмотреть реализацию


🅾️ Оценка сложности

n - количество элементов в массиве

Сложность по времени

O(n^2) так как мы запускаем цикл в цикле.

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

Сложность по памяти

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

#medium #arrays