Задача с собеседования в
Задача с собеседования в
OYO
Дан целочисленный массив nums. Верните все тройки [nums[i], nums[j], nums[k]] такие, что i != j, i != k и j != k, а также nums[i] + nums[j] + nums[k] == 0.
Обратите внимание, что результирующий набор не должен содержать дублирующиеся тройки.
Пример 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
Искомые тройки: [-1,0,1] и [-1,-1,2].
Обратите внимание, что порядок вывода и порядок троек не имеют значения.
Пример 2:
Input: nums = [0,1,1]
Output: []
Explanation: Сумма единственной возможной тройки не равна 0.
Пример 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: Единственная возможная тройка даёт в сумме 0.
Ограничения:
3 <= nums.length <= 3000
-10⁵ <= nums[i] <= 10⁵
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Для оптимального решения используем предварительную
сортировку
и
метод двух указателей
, движущихся навстречу друг другу.
После сортировки сумма будет монотонно зависеть от положения указателей: если сдвигаем l вправо - сумма не уменьшается (растёт или остаётся прежней из-за дубликатов), если сдвигаем r влево - сумма не увеличивается (уменьшается или остаётся прежней из-за дубликатов). Сортировка также упрощает обработку дубликатов, которые теперь стоят рядом.
Фиксируем первое число тройки как nums[i] и проходим переменной i по массиву nums.
Если nums[i] > 0: прерываем цикл, так как оставшиеся числа точно положительные.
Если i > 0 и nums[i] == nums[i - 1]: пропускаем текущую итерацию, так как встретили дубликат первого числа в тройке.
Инициализируем указатели:
l - указывает на эл-т, следующий за текущим i
r - указывает на последний эл-т массива
Пока l меньше r, двигаем указатели навстречу друг другу:
Вычисляем общую сумму тройки эл-в.
Если сумма больше 0:
- уменьшаем r.
Если сумма меньше 0:
- увеличиваем l.
Если сумма равна 0:
- добавляем эту тройку в res;
- сдвигаем l вправо и пропускаем дубликаты nums[l], если они есть, сдвигая l ещё раз вправо.
Возвращаем res, содержащий все уникальные тройки, сумма которых равна 0.
Сложность
O(n^2) - по времени (сортировка - O(n log n); внешний цикл - O(n), на каждой итерации i - проход двумя указателями в цикле while за O(n). Итого: O(n^2))
O(1) - по памяти (храним некоторое кол-во переменных; без учёта сортировки)
Код
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
nums.sort()
res = []
for i in range(len(nums)):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
three_sum = nums[i] + nums[l] + nums[r]
if three_sum > 0:
r -= 1
elif three_sum < 0:
l += 1
else:
res.append([nums[i], nums[l], nums[r]])
l += 1
while l < r and nums[l] == nums[l - 1]:
l += 1
return res
@algoses
Откликнуться в Telegram →
⚠️ Никогда не платите «за оформление» или «гарантию трудоустройства» — это признак мошенников. Работа ТРУ не несёт ответственности за содержание вакансии.
