计算在数组中存在总和的对数的算法

给定一个N个整数的数组。我如何计算数组的总数存在的对的数量？计算在数组中存在总和的对数的算法

E.g. int a[] = {1, 3, 4, 6, 7}。这里有三个这样的对：（1 + 3）= 4，（3 + 4）= 7，（1 + 6）= 7.

给定数组中没有重复的数字，。也可以改变数组，不需要维护数组。

我曾尝试以下两个代码，但我想减少我的代码的复杂性小于O（N^2）。

尝试1：（复杂度为O（n^3））

#include<iostream> 
#include<vector> 
#include<algorithm> 
using namespace std; 
main(){ 
    int i,input,j,n,ans=0,sum; 
    cin>>n; 
    vector<int> vec; 
    for(i=0;i<n;i++){ 
     cin>>input; 
     vec.push_back(input); 
    } 
    for(i=0;i<n;i++){ 
     for(j=i+1;j<n;j++){ 
      sum=vec[i]+vec[j]; 
      if(find(vec.begin(),vec.end(),sum)!= vec.end()){ 
       ans++; 
      } 
     } 
    } 
    cout<<ans; 
}

来源

2017-08-18 Tarun Talreja

你检查所有的对，如果他们的总和就是你增加一个计数器 – user463035818

数组中展示你的尝试和它是如何失败的。 SO不是代码写作服务 – user463035818

我增加了我的代码，同时也更新了一个问题，会有3对对于给定的数组 –

我不知道这是否会有助于降低复杂性，但我认为这是简单的这种方式，因为你不申报您正在使用，节省了内存和时间的函数的变量：

#include<iostream> 
#include<vector> 
#include<algorithm> 
using namespace std; 
bool checkForEveryElement(vector<int> vec,int sum) 
{ 
    for(int i=0; i<vec.size(); i++) 
    { 
     for(int j=i+1; j<vec.size(); j++) 
      if(vec[i] + vec[j] == sum) 
      return 1; 
    }  
    return 0; 
} 
void main(){ 
    int i,input,j,n,ans=0,sum; 
    cin>>n; 
    vector<int> vec; 
    for(i=0;i<n;i++){ 
     cin>>input; 
     vec.push_back(input); 
    } 
    sort(vec.begin(),vec.end()); 
    for(i=0;i<n;i++) 
     if(checkForEveryElement(vec,vec[i])){ 
      ans++; 
     } 
    cout<<ans; 
}

来源

2017-08-18 12:10:12 MirzaS

您已将代码的复杂度提高到O（n^3）。我想减少它不增加。 –

您可以通过使用数组或向量，所以你可以遍历一个冒泡排序算法做;因此，第一个循环（外部）从元素0开始，直到结束，内部从外部循环索引+ 1开始，以避免将元素与自身相加。并且每个内部循环我们计算元素i +元素i + 1的和。将总和存储在临时变量中。最后，最内层循环开始从i + 2只要我总结为J（I + 1），结果从第三个元素开始：

int a[] = {1, 3, 4, 6, 7}; 

for(int i(0); i < 5; i++){ 
    for(int j(i + 1); j < 5; j++){ 
     int sum = a[i] + a[j]; 
     for(int k(j + 1); k < 5; k++){ 
      if (sum == a[k]) 
       std::cout << "(" << a[i] << ", " << a[j] << "): " << sum << std::endl; 
     } 
    } 
}

*我希望这会帮助你减少所经过的时间。

来源

2017-08-19 00:18:25 Raindrop7

你做了同样的事情，并增加了我的代码到O（n^3）的复杂性。我想减少它。 –

计算在数组中存在总和的对数的算法

回答

相关问题