c++ - 给定一个排序数组和一个参数 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;

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- 时 p + s >= k t 和 s>=k/2+t。这里我们需要遍历小于 k/2 的元素并找到它们的镜像元素(二分查找)。如果镜像元素大于最后一个数组，则应停止循环。

例如我们有数组 {1,3,5,8,11} 和 k = 10，所以在第一步我们将有 k/2 = 5 和对 {5,7}，{8,11} , {8, 11}。这些对的数量将通过公式 l * (l - 1)/2 计算，其中 l = 元素数量 >= k/2。在我们的例子中 l = 3，所以计数 = 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)。

对于负数，算法会稍微复杂一些，但也可以用相同的复杂度求解。