给定两个数组a和b。找出所有满足条件a1+b1=k的元素对(a1,b1)，其中a1属于数组A，b1属于数组B。

Question

我正在寻找一种时间和空间复杂度最小的算法解决以下问题。

给定两个数组a和b，找到所有元素对(a1,b1)，其中a1属于数组A，b1属于数组B，使得它们的和a1+b1=k（任意整数）。

我能想出一个O(n log n)的方法，其中我们将数组中的一个排序，比如A，对于数组B中的每个元素b，在已排序的数组A上执行二分查找以查找值（K-b）。

我们还能进一步改进吗？

- TopCoder

---

这很可能是您可以获得的最快速的通用解决方案，因为在已排序的数组中查找n次的常数因子比对长度为n的未排序数组进行排序要低，通常情况下。因此，您可能只想对一个数组（短数组）进行排序。 - Rex Kerr

如果 a = {3, 3}, b = {7, 7}，且 k = 10，那么预期输出是什么？ - Arun

http://stackoverflow.com/questions/19175221/sum-of-two-integers-in-an-array-equals-k/24149313#24149313 - Nikhil Rupanawar

Answer 1

如果数组已排序，您可以在线性时间和恒定的存储空间内完成此操作。

• 从指向A中最小元素的指针和指向B中最大元素的指针开始。
• 计算所指向元素的总和。
• 如果比k小，则将A中的指针增加，使其指向下一个最大元素。
• 如果比k大，则将B中的指针减少，使其指向下一个最小元素。
• 如果恰好为k，则找到一对。移动其中一个指针并继续查找下一对。

如果数组最初未排序，则可以首先对它们进行排序，然后使用上述算法。有几种不同的排序方法可供选择，具体取决于您期望的数据类型：

• 比较排序，例如归并排序或Timsort。
• 计数排序。
• 基数排序。

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

- Mark Byers

---

这个算法看起来很直观，但你能证明它的正确性吗？ - damned

好的答案。另外，你好 Mark :-) - Jonas Kölker

如果 a[i] + b[j] = k，难道你不能同时更新两个指针吗？这不像是 a[i] + b[j-1] = k，除非 b[j-1] = b[j]，而在这种情况下，如果还有 a[i] = a[i+1]，那么你应该输出什么呢？更具体地说，如果 a = [1, 1]，b = [2, 2]，k = 3，那么你的输出长度应该为四吗？如果是这样，就要对所有相等值的运行进行运行长度编码，以保证不同的元素。虽然这增加了一些复杂性：现在你必须进行一些算术运算，才能确定原始数组中的索引，如果你想输出例如 [(0, 0), (0, 1), (1, 0), (1, 1)]（在我的例子中）。 - Jonas Kölker

更重要的是：在我的例子中，无论你在相等的情况下先移动哪个指针，你都会漏掉一对。我直觉地认为你可以只对一个数组进行游程编码，并移动指向另一个数组的指针，但我现在太累了，无法给出正式的证明。 - Jonas Kölker

你应该融入@Jonas的改进。此外，问题并没有规定唯一元素，但是你的答案却规定了。至少这很容易解决。 - Deduplicator

Answer 2

如果您对最大可能数量有限制（命名为 M），则可以使用 O(M+n) 的解决方案。

使用布尔数组 false 并将 A 中的所有值标记为 true。然后对于 B 中的每个元素 b，检查元素编号 K-b 是否标记为 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 倍！

- Loïc Février

---

第一个解决方案可行，但空间复杂度是M（最大可能数）的函数，而不是n。在现实世界中分配这么多空间是不可接受的。 - TopCoder

是的，我知道。但这取决于M的值。如果所有的值都在1到1000之间，但每个数组中有100万个值（未排序），那么使用它可能是有效的。这取决于问题的具体情况;) - Loïc Février

为什么你会认为使用哈希表是“作弊”呢？如果没有标准可用，你可以在10分钟内编写临时实现，并获得线性时间和空间复杂度。看起来这是最优的解决方案。无论如何，感谢提到它，点赞+1。 - Nikita Rybak

哈希表“作弊”，因为它没有改善大O，但由于平均/典型情况，似乎可以改善对幼稚的观众的印象。 - R.. GitHub STOP HELPING ICE

Answer 3

我会创建一个哈希表来存储其中一个数组的元素，然后遍历另一个数组查找 k - a(n)，如果查找成功，则生成一个输出元素。这将使用 O(n) 的空间和时间。

在 C# 中，代码可能如下所示：

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

- Gabe

Answer 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;
}

- Arun

Answer 5

我使用了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;
}

- seth_m_harden