在整数数组中找出两个数字之和相等的算法

Question

寻找整数数组中和相等的数字对的算法。

例如 {1 2 3 4 6}，输出应为 {3 2} 和 {4 1}，因为它们的和都是5。

主要问题在于复杂度应该是O(n)。如果我们找到了解决方案，请帮忙。

- sandeep

---

这个数组是否总是有序的？ - Karl Knechtel

已经给出了数对的和吗？ - Rozuur

@user281402 - 我不这么认为，例如 {1 2 3 4 6}，可能还有更多的O(n)。 - JeffO

是否保证会有 n/2 对，且最多只有一个元素没有配对？ - Dialecticus

数组{1 2 3 4 6}还有另一个解决方案：3+4，1+6。 - Dialecticus

@sandeep：你有什么要求？大多数算法可以通过进行空间/时间权衡来降低其复杂度。你的数组最多包含多少个数字？你的数组中整数的范围是什么？ - SyntaxT3rr0r

Answer 1

您确定问题在O(n)时间内可以解决吗？

想象一下输入序列只是{0, 0, 0, 0, 0, 0, ..., 0}的情况。这里每两个对都满足条件。仅列出所有对已经至少需要O(n^2)的时间。

- Vlad

---

我认为算法应该在O(n)的时间内给出是否存在一对答案，而不是拥有多于1对。 - Saeed Amiri

@Saeed：问题中明确说明输出应包含一对或多对，而不仅仅是是否存在这样的一对。让我们等待问题提出者的更新（如果有的话）。 - Vlad

是的，但我认为（就像评论中的其他人一样），OP没有澄清确切的问题，OP的示例表达了另一件事。有两个2对（如@Dialecticus所说），而OP只提到其中一个。 - Saeed Amiri

@Saaed：也许是这样，所以我们需要额外的输入。然而，OP可能只是没有自己找到这个额外的解决方案。 - Vlad

Answer 2

我认为这是可能的：

你需要一个长度为sum的第二个数组tmp = {}。

sum = 5
array = {1,2,3,4,6}
for every i in array{
    if i>=sum:
        continue
    if tmp[i] != 0 {
        output {i,(sum-i)}
        tmp[i] = 0
        continue
    }

    tmp[sum-i] := i
}

就是这样。非常简单，时间复杂度为O(n)。

缺点：

1. 它无法找到像{5,0}这样的一对，因此您必须使用真正的整数对象在第6行检查NULL并在第8行分配NULL，
2. 带有负数的对将无法工作。

- ChaosCoder

Answer 3

我不确定是否能够有效地完成这个任务。

根据给定的信息，数组未排序且您不知道需要遍历数组两次才能得到期望的总和。

考虑一种搜索算法。最简单的线性（顺序）搜索具有O(n)的复杂度。它只是用于遍历数组。如果您知道期望的总和，则情况类似，实际上您需要做的就是线性搜索。对于其他任何事情，您都会得到更高的复杂度。

但在您的情况下，您不知道总和，因此您需要多次遍历。我的想法是这是O(n log n)或O(n^2)。

也许有一种解决方案可以利用更多的数据结构，例如求和表格（2D数组？？？），但存在这样的解决方案的机会很低。

- Chathuranga Chandrasekara

---

如果您已知道总和，就没有必要寻找一对相似的数字（如您所述那么容易），因为您已经知道了它们的和是“S”，那么您如何找到类似的一对数字呢？ - Saeed Amiri

为什么使用复杂数据结构的解决方案的机会很低？你能解释一下吗？ - Vlad

Answer 4

问题在于，所述的问题似乎缺少一些有用的约束条件。首先，我想建议的是，数组的每个整数都应该是不同的。至少，输出应该是唯一的对。

另一个可能适用于特定问题域的约束条件是排序数组。当这个约束条件为真时，建议使用一个简单的算法。开始2个指针，左和右，它们各自的末尾。如果总和匹配，则输出它，增加左边并减小右边。如果不匹配，则如果总和太大，则减小右指针；如果太小，则增加左指针。继续调整左右直到它们在中间交叉。

对于未排序的数组。创建一个哈希表，插入所有整数。再次遍历数组，这次搜索哈希表以查找满足所需总和的值。如果哈希函数是完美的（这可能很棘手），则预期运行时间为O(n)。

- Timothy Prime