给定一个已排序的数组和参数k，以线性时间找到两个数字之和大于或等于k的数量

Question

我正在尝试查找数组中所有和为k的数对。我目前的解决方案需要 O(n*log(n)) 的时间（以下是代码片段）。有没有人能帮助我找到更好的解决方案，可能是 O(n) 或 O(lgn)（如果存在）

  map<int,int> mymap;
  map<int,int>::iterator it;

  cin>>n>>k;

  for( int i = 0 ; i < n ; i++ ){

    cin>>a;
    
    if( mymap.find(a) != mymap.end() )
        mymap[a]++;
    else    
        mymap[a] = 1;
        
   }

   for( it = mymap.begin() ; it != mymap.end() ; it++ ){
            
    int val = it->first;
    
    if( mymap.find(k-val) != mymap.end() ){
        
        cnt += min( it->second, mymap.find(k-val)->second );
        it->second = 0;
        
    }
    
 }
  cout<<cnt;

- SaCh

---

这个可能会有帮助。 - Karup

在着手解决问题之前，您可能会混淆复杂度O(f(n))中的n和给定的参数n。您可以考虑重新命名该参数。 此外，我认为复杂度取决于参数，让我们将其命名为k。 - Ely

由于数组已排序，当您将first和last相加并且结果太大时，应移动哪个迭代器，如果较小应该移动哪一个？ - Jarod42

@PuRaK - 这不是我想要的。我需要那些总和大于等于k的对（不仅仅是总和=k）。 - SaCh

@SakshiChauhan 在编辑后，您忘记将 "find(l-val)->second" 更改为 "find(k-val)->second"。 - Ely

Answer 1

另一种方法是针对正数的最好情况下需要O(log n)时间，最坏情况下需要O(nlog n)时间来完成：

1. 找到数组中等于k/2的元素，如果不存在，则找到大于k/2的最小元素。我们会对此元素和所有更大的元素进行组合，因为当p>=k/2且s>=k/2时，p+s>=k。由于数组已排序，因此可以使用带有一些修改的二分搜索来完成此步骤。此步骤将花费O(log n)的时间。

2. 对于小于k/2的所有元素和大于或等于“镜像元素”（根据中位数k/2）的元素，我们也会对其感兴趣，因为当p=k/2-t且s>=k/2+t时，p+s>=k。在这里，我们需要循环遍历小于k/2的元素并找到它们的镜像元素（二分搜索）。如果镜像元素大于最后一个数组，则应停止循环。

例如，我们有数组{1,3,5,8,11}和k=10，因此在第一步中，我们将得到k/2=5和配对{5,7}、{8,11}、{8,11}。这些配对的数量将通过公式l*(l-1)/2计算，其中l=count of elements>=k/2。在我们的例子中，l=3，因此count=3*2/2=3。

在第二步中，对于数字3，镜像元素将是7（5-2=3且5+2=7），因此我们会对{3,8}和{3,11}感兴趣。对于数字1，镜像将是9（5-4=1且5+4=9），因此我们要寻找{1,11}。

因此，如果k/2<第一个数组元素，则此算法的时间复杂度为O(log n)。

对于负数，算法会更加复杂，但仍然可以使用相同的复杂度来解决。

- Vasyl Zvarydchuk

Answer 2

存在一种相当简单的O(n)方法，使用所谓的“两个指针”或“两个迭代器”方法。关键思想是有两个迭代器（不一定是C++迭代器，索引也可以），在同一个数组上运行，以便如果第一个迭代器指向值x，则第二个迭代器指向小于k-x的最大元素。

我们将增加第一个迭代器，并在此过程中改变第二个迭代器以维护此属性。请注意，随着第一个指针的增加，第二个指针的相应位置只会减少，因此在每次迭代中，我们可以从上一次迭代停止的位置开始；我们永远不需要增加第二个指针。这就是我们如何实现O(n)时间复杂度。

代码如下（未经测试，但思路应该很清楚）

vector<int> a; // the given array
int r = a.size() - 1; 
for (int l=0; l<a.size(); l++) {
    while ((r >= 0) && (a[r] >= k - a[l]))
        r--;
    // now r is the maximal position in a so that a[r] < k - a[l]
    // so all elements right to r form a needed pair with a[l]
    ans += a.size() - r - 1; // this is how many pairs we have starting at l
}

另一种可能更简单编码但速度略慢的方法是使用二分搜索的 O(n log n) 算法。对于数组的每个元素 a[l]，可以使用二分搜索找到最大位置 r，使得 a[r]<k-a[l]（这与第一个算法中的那个 r 相同）。

- Petr

---

问题要求数组中两个数字的和大于k，而不是一个数组元素和k的和。我认为条件应该是（a[r]+a[l]<k）。 - glear14195

@glear14195，哦，是的，我的错。我会修正答案。 - Petr

如果你是指while条件的话，我认为我的代码是正确的。r从右往左走，所以只要a[l]+a[r]>=k，它就应该减小，这也是我代码中写的内容。 @glear14195 - Petr

明白了。不过你可能需要在while条件中添加一个缺失的括号 :) - glear14195

我认为你应该在每次迭代中重新初始化r。 - glear14195

@glear14195，不是的，这正是重点所在！数组已经排序，因此当增加l时，相应的r只会减少。如果每次重新初始化它，时间复杂度将为O(N^2)，但是利用r只会减少的事实，我们将其转化为O(N)。 - Petr

Answer 3

@Drew Dormann - 谢谢您的评论。

使用两个指针遍历数组，left和right。
假设left是小的一侧，则从位置0开始，然后right向左移动，直到最后一次a[left]+a[right] >= k。
当这个条件达成时，那么total_count += (a.size - right + 1)。
然后将left向前移动一步，right需要（可能）朝它移动。重复此过程，直到它们相遇。

完成此操作，并且假设它们在位置x相遇，则totla_count += choose(2, a.size - x)。

- shapiro yaacov

---

如果 a[left]+a[right] < n，那么将 right 向左移动仍然会得到小于 n 的结果。 - NathanOliver

@NathanOliver - 当 a[left]+a[right] 大于 n 时，当 left 向右移动一步时，right 可能向左移动仍然保持 a[left]+a[right] >= n。 - shapiro yaacov

Answer 4

1. 对数组进行排序（n log n）
2. for (i = 1 to n)
   • 从根节点开始
   • 如果 a[i] + curr_node >= k，则向左移动并匹配 = indexof(curr_nod)e
   • 否则，向右移动
   • 如果 curr_node = 叶子节点，则将 a[match] 后的所有节点添加到有效对列表中，与 a[i] 匹配

步骤2也需要 O(n log n) 的时间。循环运行 n 次。在循环内，我们对每个节点执行二分查找，即 log n 步。因此，算法的总复杂度为 O(n log n)。

- Akshar

---

数组已经排序。你想让我建立一棵树吗？ - SaCh

你不必这样做（虽然你可以）。你可以让内部循环从count = 0到log n运行，在每一步中，根据满足的条件进行i + 2 ^ count或i - 2 ^ count的操作。 - Akshar

Answer 5

这应该可以完成工作：

void count(int A[], int n) //n being the number of terms in array
{ int i, j, k, count = 0;
  cin>>k;

  for(i = 0; i<n; i++)
   for(j = 0; j<n; j++)
     if(A[i] + A[j] >= k)
      count++ ;

  cout<<"There are "<<count<<" such numbers" ;
} 

- Abhay

---

这是一种n平方的方法，是一种蛮力算法。可以更高效地完成。 - AndyG

她已经提到过，她需要比暴力破解更好的方法。 - rachitmanit