用于在求和相等的整数数组中找到数字对的算法

Question

用于在求和相等的整数数组中找到数字对的算法。 x {1 2 3 4 6}

这里{3 2} {4 1}应该是输出，因为总和是3 + 2 = 5,4 + 1 = 5。

这里最主要的是复杂性是O（n）。如果我们找到任何解决方案，请帮助我？

Answer 1

你确定O（n）中的问题完全可以解决吗？

想象一下当输入序列只是{0,0,0,0,0,0，...，0}时的情况。这里每两对满足条件。只列出所有对已经至少为O（n ^ 2）。

Answer 2

我认为这是可能的：

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

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}这样的对，因此你必须使用真实的Integer-Objects在第6行检查NULL并在第8行中指定NULL，
2. 带负数的对不起作用。

Answer 3

我不确定这是否有可能有效地完成。

根据给定的信息，数组没有排序，你不知道你需要遍历数组两次的预期总和。

想想搜索算法。在最不复杂的情况下，线性（顺序）搜索具有O（n）复杂度。它只是用于遍历数组。如果你知道你期望的总和，那么情况类似，实际上你需要做的是线性搜索。对于其他任何事情，你会获得更高的复杂

但在你的情况下，你不知道总和，所以你需要遍历不止一次。我的头说这是O（n log n）或O（n ^ 2）。

也许可能存在利用更多数据结构的解决方案，可能是求和表（2D数组），但是存在这种解决方案的可能性很低。

Answer 4

如上所述，问题似乎缺少一些有用的限制因素。第一个我想建议，数组的每个整数应该是不同的。至少，输出应该是唯一的对。

可能适用于或不适用于特定问题域的另一个约束是排序数组。当这个约束为真时，提出了一个简单的算法。从左侧和右侧开始2个指针，各自的两端。如果总和匹配，则输出，向左递增，向右递减。如果不匹配，则如果总和太大则递减右指针，或者向左递增（太小）。继续左右调整，直到它们穿过中间的某个地方。

对于未排序的数组。创建一个哈希表，插入所有整数。再次遍历数组，这次在哈希表中搜索值以满足所需的总和。如果散列函数是完美的（可能很难实现），那么预期的运行时间是O（n）。