3

所以我试图解决的问题如下：

输入是一个由 n 个数字组成的序列 {x1, x2, . . . , xn}，另一个 n 数序列 {y1, y2, . . . , yn} 和一个数字 z。您的算法应确定 z ∈ {xi + yj | 1≤i，j≤n}。您应该使用通用散列系列，并且您的算法应该在预期时间 O(n) 内运行。

提供理由证明您的算法是正确的并在要求的时间内运行。非常清楚您正在使用的课程和/或文本中的哪些定理，以及如何使用。

到目前为止，我已经提出了这个算法来查找所有可能的总和，将它们插入到哈希表中，然后搜索z：

for (i in x; i++) {
    for (j in y; j++) {
        sum = xi + yj;
        insert_into_hash_table(T, sum);
    }
}

search_hash_table(T, z);

唯一的问题是这里最坏情况的时间是O(n^2)。

我该怎么做O(n)？=S

4

2 回答 2

3

只需将所有内容放在Yi 一个map.

现在一旦你有Z：

 for all values from Xi
     find if Z - Xi os present in map
于 2013-11-11T21:03:14.220 回答
0

您可以将 x 的所有数字插入到哈希表 T 中，并确定 (Zy) 是否在 T 中。这需要对 X 进行扫描，对 Y 进行一次扫描。

T = set()
for x in X:
    T.add(x)
for y in Y:
    if (Z-y) in T:
        return TRUE
于 2013-11-11T21:05:23.397 回答