Это решение требует предварительной сортировки массива в возрастающем порядке, поэтому первым делом выполняем сортировку.
Далее мы можем заметить, что задача очень похожа на ее более простой аналог — Сумма двух чисел в массиве. Разница только в том, что нам надо найти все тройки, а их сумма всегда равно нулю. Мы можем воспользоваться подходом из этой задачи и решить ее через дополнительную структуру HashSet или ее аналоги.
Посмотрим на такой пример ввода
[-1, 0, 1, 2, -1, -4].После сортировки мы получим следующий массив
[-4, -1, -1, 0, 1, 2].Теперь запускаем цикл по всем элементам массива.
Далее для каждого i-го элемента мы будем запускать отдельный цикл для поиска недостающей пары чисел из тройки. Так как мы всегда двигаемся слева направо, то мы можем запускать второй цикл начиная от i + 1 и до конца.
Первое, что нам нужно учесть — это то, что в наших ответах не должно быть одинаковых троек. Если мы посмотрим еще раз на пример входящих данных, то мы обнаружим что у нас есть два одинаковых возможных решения [-1, 0, 1].
В массиве есть две возможные тройки с такими значениями под индексами
1, 3, 4 и 2, 3, 4. Однако, это легко решить, так как у нас отсортированный массив. Это значит, что одинаковые значения идут подряд и мы просто можем проверять первое и пропускать все остальные.
Добавим проверку в самое начало первого цикла. Если мы перебираем не первый элемент в массиве и текущий элемент равен предыдущему, то мы просто его пропускаем. И дополнительно создадим Set для отслеживания уже проверенных чисел.
Осталось решить, что делать внутри второго цикла. Нам нужно вычислить третье число, которого не хватает, чтобы получить в сумме ноль и проверить, встречалось ли уже такое число в нашем массиве. Для проверки мы как раз и используем Hash Set.
- Если третье число есть в Hash Set, то мы добавляем в наш результат массив из всех трех полученных чисел.
- Если третьего числа нет в Hash Se, то мы просто записываем в него второе число и идем дальше.
Осталось учесть еще один нюанс. Во время перебора второго массива мы тоже можем получать одинаковые значения и тем самым создавать дубликаты. Поэтому, после добавления найденной тройки нам надо увеличивать j до тех пор, пока значение под индексом j равно значению под индексом j - 1.
В результате мы получаем следующее решение задачи.
Посмотреть реализацию
🅾️ Оценка сложности
n - количество элементов в массиве
Сложность по времени O(n^2), так как мы запускаем цикл в цикле. Дополнительную сложность добавляет сортировка массива, она будет равна
O(nlogn). Итоговая сложность равна O(nlogn + n^2), что асимптотически эквивалентно O(n^2).Сложность по памяти O(n), так как мы добавляем в сет
n элементов.#medium #arrays