我在find中遇到了一个编程问题，我必须在给定的未排序数组中找到所有对，以便
|i - j| <= K and |A[i] - A[j]| <= x
例如:
A = {5,4,8,3} and x = 3 and k = 2.
答案:(5,4), (5,8), (4,3)
我已经尝试了很多次，但无法想到任何时间复杂度低于O(nk)的算法。我也试过平衡二叉树，但它没有帮助我。
编辑:如果我们必须找到这样的对在数组中是否存在(这意味着只有一个这样的对)，我们可以做一些好事吗?
取前N-1项，并对它们进行排序。这就给出了最小/最大和前几对。然后，对于列表中的每个条目，它是根据min/max匹配部分、全部还是不匹配?如果没有匹配或全部匹配，你就可以直接配对了。如果匹配，就进行二分搜索来找到分界点。然后删除第一个条目并添加新条目，使用平衡二叉树保存排序列表。
所以你是O(N log k)，在实践中，开销将会非常高，不太可能打败朴素的O(Nk)方法。