配列に合計が存在するペアの数を数えるアルゴリズム

Question

N個の整数の配列が与えられているとします。配列に合計が存在するペアの数をどのように数えることができますか？

など。 int a[] = {1, 3, 4, 6, 7}。 （3 + 4）= 7、（1 + 6）= 7

指定された配列に重複する数字はなく、配列はソートされませんまた、アレイを変更することができ、アレイを維持する必要はありません。

私は以下の2つのコードを試しましたが、私のコードの複雑さを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; 
} 

Answer 1

私は、これは複雑さを減らすのに役立ちますかどうかわからないんだけど、私はあなたが宣言していないので、それはこのように簡単だと思いますあなたが使用している関数内の任意の変数、メモリと時間を節約：あなたはバブルソートアルゴリズムとして反復できるよう

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

Answer 2

あなたは配列やベクターを使用してそれを行うことができます。したがって、最初のループ（外側）は要素0から終わりに始まり、内側が始まると外側ループindex + 1が要素を合計することを避けます。そして、各内部ループは、要素i +要素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; 
     } 
    } 
} 

：最後に、最も内側のループは限り私はjに加算された第（i + 1）と結果は第三の要素から始めるとI + 2から始まります。