找到使得|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) 时间内完成呢？

- Vedant Dixit

---

请不要描述您的代码，尝试创建一个最小、完整和可验证的示例来展示给我们。 - Some programmer dude

我认为你的算法不完整。如果我的数组是 [1, 2, 3, 5, 8] 并且 k=4，那么你的解决方案应该是 i=0, j=3，但是你找不到它。 - scohe001

什么是“给定的总和”？ - meowgoesthedog

如果没有abs，我会同意你的看法，但在一个最小化问题中，abs改变了一切。我们实际上正在寻找一个数组中两个值的和最接近k的总和。（因此，k在这里实际上非常重要） - scohe001

@AbhishekKeshri 使用 unordered_map，你可以在 O(log(n)) 的时间内找到与你正在查找的任何值最接近的值，以形成可能的一对，但你仍然需要循环遍历数组中的所有值。使用该算法的最短时间将是 O(nlog(n))。 - scohe001

Answer 1

假设在任何排序之后都需要O(n)的要求（或者您的问题领域支持线性时间排序），则可以对双指针算法进行微小变化（即使在有两个不同数组的情况下，其中一个可能不需要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排序；该问题是一种“X+Y二分搜索”。

- Davis Herring

---

我认为你没有理解问题。不要改变问题来适应你自己的需求。问题本身已经很清楚了。 - Vedant Dixit

@VedantDixit：我问了一个澄清问题，但没有得到答案。由于显然不可能使用（比较）排序来实现线性时间算法，而且我确信（没有证明）在不排序的情况下无法更快地解决该问题，因此我编辑了问题以用这些术语表达，_而不排除有人比我更聪明地解决它而不排序。你认为我在问题意图上还做了什么改变？ - Davis Herring

你的“排除”操作是否隐藏了你没有聚合的复杂性？如何找到要“排除”的元素范围的过程是什么？ - גלעד ברקן

回复 @גלעדברקן：排除表的一部分只意味着您不沿着那个方向进行探索。实际上，内存中没有改变O(n^2)大小的表。 - Davis Herring

你还没有回答我的问题，“找到要在每次迭代中“排除”的元素范围的过程是什么，它是否隐藏了额外的复杂性？” - גלעד ברקן