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 值。