在O(n)时间和O(1)空间中输出数组编号及其求反

Question

给定一个整数数组。如果数组中同时存在数字a及其求反-a，则打印它。例如:如果给定{10，5，0，9，-10，7，- 5 }，则打印10，5。我给了面试官基于HashMap的O(N)时间和O(N)空间复杂度代码，但他进一步要求我在最坏的情况下将空间复杂度降低到O(1)，保持时间复杂度O(N)。注意:不允许计数排序。有人能给我提供O(1)空间复杂度的方法吗？

Answer 1

如果数组元素是无序的并且在任意范围内，则这在O(n)时间和O(1)空间中是不可能的。如果数组被排序，我们可以使用两个指针在这些约束下求解它。