algorithm - 从两个长度为 n 的数字序列中找出所有可能的和，并在 O(n) 时间内将它们插入到哈希表中？

Question

所以我要解决的问题如下:

The input is a sequence of n numbers {x1, x2, . . . , xn}, another sequence of n numbers {y1, y2, . . . , yn}, and a number z. Your algorithm should determine whether or not z ∈ {xi + yj | 1 ≤ i, j ≤ n}. You should use universal hashing families, and your algorithm should run in expected time O(n).

Provide justification that your algorithm is correct and runs in the required time. Be very clear about which theorems from class and/or the text you are using, and how.

到目前为止，我已经想出了这个算法来找到所有可能的和，将它们插入到哈希表中，然后搜索 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

Answer 1

只需将所有Yi 放入map 即可。

现在一旦你有了Z:

 for all values from Xi
     find if Z - Xi os present in map