Сумма трёх чисел
Дан массив целых чисел nums
. Верните все возможные тройки чисел [nums[i], nums[j], nums[k]]
, где nums[i] + nums[j] + nums[k] = 0
, и индексы i
, j
и k
различны.
Результат не должен содержать повторяющихся троек чисел. Вы можете вернуть тройки в любом порядке.
Пример 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Объяснение:
nums[0] + nums[2] + nums[1] = (-1) + 1 + 0 = 0
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0
Пример 2:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Рекомендуемая временная и пространственная сложность
Оптимальное решение имеет временную сложность O(n²) и пространственную сложность O(1) или O(n), где n — размер входного массива.
Подсказка 1
Сортировка массива в начале может помочь избежать дубликатов и упростить поиск нужных троек чисел.
Подсказка 2
После сортировки можно использовать технику двух указателей для каждого фиксированного элемента, чтобы найти оставшиеся два числа.
Подсказка 3
Для избежания дубликатов, пропускайте повторяющиеся значения при переборе фиксированного элемента и при движении указателей.