给定两个数组a和b。找到所有对元素(a1,b1)， a1属于数组a,b1属于数组b，其总和a1+b1 = k。

I am looking for the solution of following algorithm with minimal time and space complexity.

我正在寻找的解决方法，以最小的时间和空间复杂度的算法。

Given two arrays a and b, find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k (any integer).

给定两个数组a和b，找到所有的元素对(a1,b1)， a1属于数组a,b1属于数组b，它的和是a1+b1 = k(任意整数)。

I was able to come up with O(n log n) approach where we will sort one of the array say A and for each of the element b in array B, do binary search on sorted array A for value (K-b) .

我可以提出O(n log n)的方法，在数组b中，我们将对其中一个数组进行排序，对数组b中的每一个元素b，进行二进制搜索，对数组A的值进行排序(K-b)。

Can we improve it any further?

我们能进一步改进吗?

5 个解决方案

#1

If you have a limit on the maximum possible number (let's name it M) then you can have a solution in O(M+n).

如果你对最大可能数有一个限制(让我们命名为M)，那么你可以在O(M+n)中得到一个解。

Boolean array of false and mark as true all value for element of A. Then for each element b of B check if the element number K-b is marked as true.

对于a元素的所有值，如果a元素的K-b被标记为true，那么对a元素的所有值都为true。

You can improve it if you are using an hash-map instead of a big array. But I would not consider that in this kind of questions hash-map is kind of cheating.

如果您使用的是hashmap而不是大数组，您可以改进它。但我不认为在这类问题中，hashmap是一种欺骗。

Anyway it would give you O(n) for insertion and then O(n) for query, O(n) in total.

无论如何，它会给你O(n)插入，然后O(n)用于查询，O(n)总共。

EDIT :

编辑:

One case where this might be useful.

这可能是有用的。

You have un-sorted vectors of size 10^6, so sorting them and doing the match is in O(n log n) with n = 10^6.
un-sorted向量的大小10 ^ 6,所以排序和匹配在O(n log n)与n = 10 ^ 6。
You need to do this operation 10^6 times (different vectors), complexity of O(n*n*log n).
你需要做这个操作10 ^ 6 *(不同的向量),复杂的O(n * n * O(log n))。
Maximum value is 10^9.
最大值是10 ^ 9。

Using my idea not with boolean but integer (incremented at each run) gives you a complexity of :

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

"O(10^9)" to create the array (also same complexity of space)
“O(10 ^ 9)”创建数组(也同样复杂的空间)
O(n) at each run, so O(n*n) for the total.
O(n)在每次运行时，O(n*n)为总数。

You are using more space but you've increased speed by a factor log(n) ~=20 in this case !

您正在使用更多的空间，但是您已经提高了速度的一个因素log(n) ~=20在这种情况下!

#2

If the arrays are sorted you can do it in linear time and constant storage.

如果数组被排序，你可以在线性时间和常量存储中完成。

Start with two pointers, one pointing at the smallest element of A, the other pointing to the largest element of B.
从两个指针开始，一个指向A的最小元素，另一个指向B的最大元素。
Calculate the sum of the pointed to elements.
计算指向元素的和。
If it is smaller than k increment the pointer into A so that it points to the next largest element.
如果它小于k，则将指针变成A，这样它就指向下一个最大的元素。
If it is larger than k decrement the pointer into B so that it points to the next smallest element.
如果它大于k，将指针移到B中，这样它就指向下一个最小的元素。
If it is exactly k you've found a pair. Move one of the pointers and keep going to find the next pair.
如果恰好是k你就找到了一对。移动其中一个指针，然后继续寻找下一对。

If the arrays are initially unsorted then you can first sort them then use the above algorithm. There a few different approaches for sorting them that you could use, depending on the type of data you expect:

如果数组最初是未排序的，那么您可以首先对它们进行排序，然后使用上面的算法。根据您所期望的数据类型，有几种不同的方法来对它们进行排序。

A comparison sort, e.g. Mergesort or Timsort.
比较排序，例如归并排序或时间排序。
Counting sort.
计数排序。
Radix sort.
基数排序。

A comparison sort will require O(n log n) time on average. The last two are faster than O(n log(n)) but can be impractical if the range of possible values in the input arrays is very large.

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

#3

I would create a hash table containing the elements of one array, then iterate the other array looking up k - a(n), generating an output element if the lookup succeeded. This will use O(n) space and time.

我将创建一个包含一个数组元素的散列表，然后迭代另一个数组，查找k - a(n)，如果查找成功，生成一个输出元素。这将使用O(n)空间和时间。

In C#, it might look like this:

在c#中，它可能是这样的:

var bSet = new HashSet(B);
var results = from a in A
              let b = k - a
              where bSet.Contains(b)
              select new { a, b };

#4

template< typename T >
std::vector< std::pair< T, T > >
find_pairs( 
    std::vector< T > const & a, std::vector< T > const & b, T const & k  ) {

    std::vector< std::pair< T, T > > matches;

    std::sort( a.begin(), a.end() );  // O( A * lg A )
    std::sort( b.begin(), b.end() );  // O( B * lg B )

    typename std::vector< T >::const_iterator acit = a.begin();
    typename std::vector< T >::const_reverse_iterator bcit = b.rbegin();

    for( ; acit != a.end(); /* inside */ ) {
        for( ; bcit != b.rend(); /* inside */ ) {

            const T sum = *acit + *bcit;

            if( sum == k ) {
                matches.push_back( std::pair< T, T >( *acit, *bcit ) );
                ++acit;
                ++bcit;
            }
            else if( sum < k ) {
                ++acit;
            }
            else {  // sum > k
                ++bcit;
            }
        }
    }  // O( A + B )
    return matches;
}

#5

I used C++ and it seemed to give me the desired result. Hope this is what you were looking for.

我用了c++，它似乎给了我想要的结果。希望这就是你想要的。

using namespace std;

using data=std::pair<int,int>;

void search_pairs(std::vector<int>& A, std::vector<int>& B, const int total, std::vector<data>& output){

  std::sort(A.begin(),A.end(),[](const int i,const int j)->bool{return (i<j);});
  std::sort(B.begin(),B.end(),[](const int a,const int b)->bool{return (a<b);});
  std::vector<int>* minV(nullptr);
  std::vector<int>* maxV(nullptr);
  if(A.size()>B.size()) {minV=&B;maxV=&A;}
  else {minV=&A;maxV=&B;}
  for(auto&& itr:(*minV) ){
    auto remain(total-itr);
    if (std::binary_search (maxV->begin(), maxV->end(), remain)){
      data d{itr,remain};
      if (minV==&B) std::swap(d.first,d.second);
      output.push_back(d);
    }
  }
  if (minV==&B) std::reverse(output.begin(),output.end());  
}

int main() {

    size_t nb(0);
    scanf("%lu",&nb);
    for (size_t i=0;i<nb;++i){
        size_t a,b(0);
        int total(0);
        scanf("%lu %lu %d",&a,&b,&total);
        std::vector<int> A,B;
        for (size_t i=0;i<a;++i){
            int aux;
            scanf("%d",&aux);
            A.push_back(aux);
        } 
        for (size_t i=0;i<b;++i){
            int aux;
            scanf("%d",&aux);
            B.push_back(aux);
        } 
        std::vector<data> output;
        search_pairs(A, B, total, output);
    auto itr=std::begin(output);
    if (itr==std::end(output)) printf("-1"); 
    while (itr!=std::end(output)){
      printf("%d %d",(*itr).first, (*itr).second);
      if (++itr!=std::end(output)) printf(", ");
    }
        printf("\n");
    }
    //code
    return 0;
}

#1