Почему это работает
- Зафиксируем одно число, nums[i], — тогда два других должны дать в сумме -nums[i]. В отсортированном массиве это Two Sum II: left и right идут навстречу, и каждый сдвиг отбрасывает число навсегда.
- После сортировки одинаковые числа стоят рядом, поэтому повтор легко заметить. Если nums[i] равно предыдущему числу, его тройки уже найдены, и i его пропускает; после найденной тройки left так же перешагивает копии её среднего числа.
- Каждая тройка находится один раз — когда i впервые встаёт на её самое маленькое число: цикл перебирает все первые числа, а поиск пары видит все пары правее.
Сложность
Время O(n²): сортировка занимает O(n log n), а потом для каждого из n значений i указатели проходят остаток массива один раз. Память O(1) без учёта ответа: массив сортируем на месте, а для повторов не нужно множество.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗