我正在寻找具有最小时间和空间复杂性的以下算法的解决方案.
给定两个数组a和b,找到所有元素对(a1,b1),使得a1属于数组A,b1属于数组B,其和a1 + b1 = k(任何整数).
我能够提出O(n log n)方法,我们将其中一个数组排序为A,对于数组B中的每个元素b,对排序数组A进行二进制搜索以获得值(Kb).
我们可以进一步改进吗？
可能重复:
给定两个数组a和b.查找所有元素对(a1,b1),使得a1属于数组A,b1属于数组B,其总和a1 + b1 = k.
给定:未排序A的整数数组
输入:整数k
输出:所有两个元素集合,每个元素的总和等于kO(n).
例:
A = {3,4,5,1,4,2}
输入:6
输出:{3,3}, {5,1}, {4,2}
注意:我知道一个O(n logn)解决方案,但这需要对数组进行排序.有没有办法在O(n)中解决这个问题.可以使用非平凡的C++数据结构,即空间没有界限