Сумма трех чисел в массиве. Решение через два указателя

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

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

Теперь запускаем цикл по всем элементам массива.

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

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

Теперь мы можем полностью скопировать решение из задачи Сумма двух чисел в отсортированном массиве и немного его модифицировать.

1. Заводим два указателя, которые будут хранить индексы. Значение left делаем равным i + 1, значение right равным индексу последнего элемента.

2. Запускаем цикл, который прервется, если left станет больше или равен right, то есть когда индексы сойдутся.

3. На каждой итерации высчитываем сумму элементов под индексами left, right и i-го элемента массива и проверяем ее на равенство нулю.

🔹 Если сумма больше нуля, значит мы сложили слишком большие числа и нам надо взять более маленькие. Уменьшить сумму мы можем взяв число, которое стоит левее от текущего под индексом right. Уменьшаем right на 1.

🔹 Если сумма меньше нуля, значит мы сложили слишком маленькие числа и нам надо взять более большие. Увеличить сумму мы можем взяв число, которое стоит правее от текущего под индексом left. Увеличиваем left на 1.

🔹 Если сумма равна нулю, значит мы нашли искомые числа. В таком случае добавляем найденную тройку nums[i], nums[left] и nums[right] в коллекцию ответов. Здесь же сразу уменьшаем right и увеличиваем left на единицу, чтобы найти следующую возможную комбинацию.

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

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


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

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

Сложность по времени O(n^2), так как мы запускаем цикл в цикле. Дополнительную сложность добавляет сортировка массива, ее сложность равна O(nlogn). Итоговая сложность равна O(nlogn + n^2), что асимптотически эквивалентно O(n^2).

Сложность по памяти варьируется от O(logn) до O(n) в зависимости от реализации алгоритма сортировки. На хранение указателей мы тратим константную память O(1), поэтому финальная сложность по памяти определяется сложностью алгоритма сортировки.

#medium #arrays