The problem is the following: We are given a number 's', s ∈ [0, 10^6], and a number 'n', n ∈ [0, 50000], then n numbers, and we have to find how many number pairs' sum is equal to the 's' number (and we must use either maps or sets to solve it)

Here is the example:

Input:

5 (this is s)
6 (this is n)
1 
4 
3 
6 
-1 
5 

Output:

2

explanation : these are the (1,4) and (6,−1) pairs. (1 4 = 5 and 6 (-1) = 5)

Here is my "solution" , I don't even know if it's correct, but it works for the example that we got.

#include <iostream>
#include <map>
#include <iterator>
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int s;
    cin >> s;
    int n;
    cin >> n;
    map<int, int> numbers;

    int element;
    int counter = 0;
    for(int i=0; i<n;i  )
    {
        cin >> element;
        numbers.insert(pair<int, int>(element, s-element));

    }
    for(map<int, int>::iterator it = numbers.begin(); it != numbers.end(); it  )
    {
        map<int, int>::iterator it2 = it;
        while(it2 != numbers.end())
        {
            if(it->second == it2->first)
            {
                counter  ;
                break;
            }
            it2  ;

        }
    }
    cout << counter << "\n";
    return 0;
}

Thanks for the answers in advance! I'm still a beginner and I'm learning, sorry.

CodePudding user response：

element, s-element is a good idea but there is no reason to store all the pairs and only then check for duplicates. This removes the O(n^2) loop you have there at the end.

The standard way using hashing would be:

seen=unordered_map<number,count>() 
for 1...n:
  e = read_int()
  if (s-e) in seen:
    duplicates =seen[s-e] # Found new seen[s-e] duplicates.
  if e in seen:
    seen[e] =1
  else:
    seen.insert(e,1)

return duplicates

CodePudding user response：

Here's a brute-force method, using a vector:

int target_s = 0;
int quantity_numbers = 0;
std::cin >> target_s >> quantity_numbers;
std::vector<int> data(quantity_numbers);
for (int i = 0; i < quantity_numbers;   i)
{
    cin >> data[i];
}

int count = 0;
for (int i = 0; i < quantity_numbers;   i)
{
    for (j = 0; j < quantity_numbers;   j)
    {
        if (i == j) continue;
        int pair_sum = data[i]   data[j];
        if (pair_sum == target_s)   count;
    }
}
std::cout << count;

The above code includes the cases where pair <a,b> == s and pair <b,a> == s. Not sure if the requirement only wants pair <a,b> in this case.