finding two pairs of numbers, which makes A+B = C+ D.

find_double_twosum.cpp

#include<vector>
#include<map>
#include<iostream>

using namespace std;

struct node {
  int x;
  int y;
  int sum;
  node(int a, int b, int s):x(a), y(b), sum(s){}
};

map<int, int> build_hashtable(vector<int>& input)
{
  map<int, int> hashtable;
  for (int i = 0; i< input.size(); i++)
  {
    hashtable[input[i]] = i;
  }
  return hashtable;
}

vector<node*> build_sum_list(vector<int>& input)
{
  vector<node*> sums;
  for (int i = 0; i<input.size(); i++)
  {
    for(int j = i+1; j < input.size(); j++)
    {
      sums.push_back(new node(i,j, input[i]+input[j]));
    }
  }
  return sums;
}
vector<int> find_double_sum(vector<int>& input)
{
  vector<int> result;
  map<int, int> hashtable = build_hashtable(input);
  vector<node*> sums = build_sum_list(input);

  for ( int i = 0; i< sums.size(); i++)
  {
    int sum = sums[i]->sum;
    for (int j = 0; j < input.size(); j++)
    {
      map<int, int>::iterator found;
      if (j != sums[i]->x && j != sums[i]->y)
      {
        if ((found = hashtable.find(sum-input[j]))!= hashtable.end())
        {
          result.push_back(sums[i]->x);
          result.push_back(sums[i]->y);
          result.push_back(j);
          result.push_back(found->second);
          return result;
        }

      }
    }
  }
  return result;
}

int main()
{
  vector<int>input;
  input.push_back(3);
  input.push_back(4);
  input.push_back(7);
  input.push_back(1);
  input.push_back(2);
  input.push_back(9);
  input.push_back(8);

  vector<int>result = find_double_sum(input);
  for (int i = 0; i < result.size(); i++)
    cout<<" "<<result[i]<<", ";
  cout<<endl;
  return 1;
}