algorithm - 给定一个数组，找出是否有 2 个数字的差为 c

Question

我有这个问题的 O(n ² ) 解决方案，想知道是否有更好的解决方案。如果我们试图找到 2 个数字，其和为 c，那么我知道有一个 O(nlogn) 解决方案。（在这里给出）我在这里尝试类似的方法：我首先在 O(nlogn) 时间内使用合并排序对数组进行排序，然后从数组的两端开始，并查看它们的差异。如果这等于 c，那么我们就完成了。如果差值大于 c，那么我将最右边的索引减 1，但我认为这是错误的，我们不知道是确实减少了最右边的索引还是必须增加了最左边的索引。我对吗？我们能以更好的时间复杂度解决这个问题吗？谢谢

Answer 1

他们的关键是，一旦对数组进行排序，二分查找就只有O(logn).

对于数组中的每个数，通过二分查找来x测试是否在数组中。x-c这还是O(nlogn)。

如果你想花哨，你可以通过数组迭代两次来做到这一点，但复杂性无论如何都由排序步骤决定。

Answer 2

我的方法，使用哈希和no need for pre-sorting，它取决于哈希实现，在最好的情况下它可以在 O(n) 中完成，在最坏的情况下 O(nlogn)，

arr[] = { ... }
hash[] // maps Integer to Boolean
for e in arr:
    hash[e] = true
    if hash[e+c] == true Or hash[e-c] == true:
        return true
return false

遍历数组，对每个元素e执行：

• e在哈希中映射为 true
• 如果存在与c当前元素不同的元素，则 Bingo :D

希望这可以帮助 ：）

Answer 3

您可以对需要 O(n log n) 时间的数组进行排序。然后，您可以通过将第一个中的每个成员 x 替换为 c - x，然后反转来创建第二个数组。然后，您可以查看这两个数组是否有一个共同的元素，每个元素都需要两次遍历 O(n)。