arrays - 在数组中查找所有差异为 's' 的对

Question

我有一个长度为 n 的数组，整数在 [0,n^5] 范围内。我想在数组中找到所有对，它们之间的差异是给定的值为s的整数变量(例如，对于数组中的整数a，b，我们如果他们满足给定的要求，将有 a-b=s 或 b-a=s)。

找到所有对的最佳确定性算法(即不使用哈希集或相似性)是什么？我可以在 O(n) 时间复杂度内完成吗？

我的想法是首先在 O(n) 时间内用 Radix-Sort 对数组进行排序，然后使用数组已排序的事实以某种方式找到所有对但我不确定如何实现。

谢谢。

Answer 1

一旦用基数排序对数组进行排序(假设输入复杂度为 O(n))，您可以使用双指针方法，其中 p1 和 p2 都位于数组的开头，然后遍历数组直到 p2 < number数组中元素的个数

粗略的伪代码..

while p2 < array.length && p1 < array.length
  if array[p2] - array[p1] == k
    increment count of unique pairs
    increment p1
    increment p2
  else if array[p2] - array[p1] > k
    increment p1
  else 
    increment p2
  end
end

编辑: p1 < array.length对于负 s 值。