Вывести номера массивов с их отрицанием в O (n) времени и O (1) пространстве

Question

Дан массив целых чисел.Если число a и его отрицание -a присутствуют в массиве, выведите его.Например: если задано {10, 5, 0, 9, -10, 7, -5}, выведите 10, 5. Я дал интервьюеру O (N) время и O (N) код сложности пространства на основе HashMap, но ондалее попросил меня уменьшить сложность пространства до O (1) в худшем случае, сохраняя сложность времени O (N).Примечание. Подсчет сортировки не разрешен.Пожалуйста, кто-нибудь может дать мне подход к сложности пространства O (1)?

Answer 1

Это невозможно в O(n) времени и O(1) пространстве, если элементы массива неупорядочены и находятся в произвольном диапазоне.Если массив отсортирован, мы можем решить его в рамках этих ограничений, используя два указателя.