algorithm - 第一对数字添加到流中的特定值

Question

有一个整数流通过。问题是从流中找到添加到特定值(例如，k)的第一对数字。

对于静态数组，可以使用以下任一方法:

• 方法(1):对数组进行排序，使用指向数组首尾的两个指针进行比较。
• 方法 (2):使用哈希，即如果 A[i]+A[j]=k，则 A[j]=k-A[i]。在哈希表中搜索 A[j]。

但是这两种方法都不能很好地扩展到流。对有效解决这个问题有什么想法吗？

Answer 1

我相信，如果不使用至少 O(n) 内存，就无法做到这一点，其中 n 是出现在第一对总和为 k 之前的元素数。我假设我们使用的是 RAM 机器，而不是一台允许可怕的按位黑客攻击的机器(换句话说，我们不能对位打包做任何花哨的事情。)

证明草图如下。假设我们不存储出现在总和为 k 的第一对之前出现的所有 n 个元素。然后当我们看到第 n 个元素，它与之前的某个值相加得到 k 时，我们有可能已经丢弃了与之配对的前一个元素，因此不知道已经达到了 k 的总和。更正式地说，假设当我们查看前 n - 1 个元素并注意到我们没有存储某些元素 x 时，对手可以查看我们在内存中存储的值。然后对手可以将流的下一个元素设置为 k - x，我们会错误地报告尚未达到总和，因为我们不记得看到过 x。

鉴于我们需要存储我们看到的所有元素，而无需更多地了解流中的数字，一个非常好的方法是使用包含我们目前看到的所有元素的哈希表.给定一个好的哈希表，这将花费预期的 O(n) 内存和 O(n) 时间来完成。

如果你对流中的数字种类做出更强的假设，我不确定是否有更聪明的策略来解决这个问题，但我相当有信心这在时间和空间方面是渐近理想的。

希望这对您有所帮助!