给定两个数组a和b.找出所有元素对(a1,b1),使得a1属于数组A,b1属于数组B,其总和a1 + b1 = k

Question

我正在寻找具有最小时间和空间复杂性的以下算法的解决方案.

给定两个数组a和b,找到所有元素对(a1,b1),使得a1属于数组A,b1属于数组B,其和a1 + b1 = k(任何整数).

我能够提出O(n log n)方法,我们将其中一个数组排序为A,对于数组B中的每个元素b,对排序数组A进行二进制搜索以获得值(Kb).

我们可以进一步改进吗？

Answer 1

如果对数组进行排序,则可以在线性时间和常量存储中进行排序.

• 从两个指针开始,一个指向A的最小元素,另一个指向B的最大元素.
• 计算指向元素的总和.
• 如果小于k,则将指针增加到A,使其指向下一个最大元素.
• 如果它大于k,则将指针递减到B,使其指向下一个最小元素.
• 如果它恰好是k,你就找到了一对.移动其中一个指针,继续寻找下一对.

如果数组最初未排序,那么您可以先对它们进行排序,然后使用上述算法.根据您期望的数据类型,可以使用几种不同的方法对它们进行排序:

• 比较排序,如归并或Timsort.
• 数排序.
• 基数排序.

比较排序平均需要O(n log n)时间.最后两个比O(n log(n))快,但如果输入数组中可能值的范围非常大,则可能不切实际.

Answer 2

如果您对最大可能数量有限制(让我们将其命名为M),那么您可以在O(M + n)中找到解决方案.

布尔数组为false,mark为true,为A元素的所有值.然后,对于B的每个元素b,检查元素编号Kb是否标记为true.

如果使用散列映射而不是大数组,则可以改进它.但我不认为在这种问题中,哈希图是一种作弊行为.

无论如何,它会给你O(n)插入,然后O(n)用于查询,O(n)总计.

编辑:

一个可能有用的案例.

• 你有未分类的大小为10 ^ 6的向量,所以对它们进行排序并进行匹配是在O(n log n)中,n = 10 ^ 6.
• 你需要做这个操作10 ^ 6次(不同的向量),复杂度为O(n*n*log n).
• 最大值为10 ^ 9.

使用我的想法不是布尔而是整数(每次运行时增加)会给你一个复杂性:

• "O(10 ^ 9)"创建数组(同样复杂的空间)
• 每次运行O(n),所以O(n*n)为总数.

您正在使用更多空间,但在这种情况下,您的速度增加了因子log(n)〜= 20!