java - 在 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) 空间内是不可能的。如果数组已排序，我们可以使用两个指针在这些约束内解决它。