Задача с собеседования в

Задача с собеседования в 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