c++ - 寻找 abs(A[i]+A[j]-k) 最小值的算法

Question

我有一个包含正数和负数的整数数组A。我必须找到 abs(A[i] + A[j] - k) 的最小值，其中 i != j。

我想到了对数组进行排序并使用两指针方法(如 https://www.geeksforgeeks.org/two-pointers-technique/ 中所述)并找到最小值。时间复杂度为 O(n*log(n))。这可以在 O(n) 中完成吗？

Answer 1

假设 O(n) 要求适用于任何排序(或者您的问题域支持 linear-time sorting )，您可以对两指针算法使用一个简单的变体(即使对于有两个不同数组的情况，其中一个可能不需要 i!=j)。考虑布置在矩形中的两个排序数组的元素总和:

    A= 4  9 17 22 29
 B= 7 11 16 24 29 36
   19 23 28 36 41 48
   20 24 29 37 42 49
   35 39 44 52 57 64

假设 k=40。通过检查最左下角的值(较小的值)，我们可以立即排除包含最接近值的列的大部分，因为这些值必须甚至更小:

    A= 4  9 17 22 29
 B= 7    16 24 29 36
   19    28 36 41 48
   20    29 37 42 49
   35 39 44 52 57 64

所以我们接下来检查右边的值(也就是说我们将指针递增到 A)。它大于 k，因此它消除了该行的其余部分:

    A= 4  9 17 22 29
 B= 7    16 24 29 36
   19    28 36 41 48
   20    29 37 42 49
   35 39 44

下一步必须是--b。继续这种方式，通过矩形切出一条路径:

    A= 4  9 17 22 29
 B= 7          29 36
   19          41
   20    29 37 42
   35 39 44

您可以在完全匹配时向任一方向(或对角线)移动(或者如果一次命中就足够了，则可以提前保释)。通常，路径可能会在拐角处以外的地方退出矩形。对于只有一个数组的情况，您可以在它到达对角线时立即停止(即，当 i>=j 时)，忽略最后一步到的任何值。

这条路径显然有 O(n) 个条目，因为它在每一步都向上或向右(或两者)移动。其中之一必须最接近 k(这里，4+35 和 22+19 并列)。

另见 X+Y sorting ;这个问题是一种“X+Y 二进制搜索”。