получить неправильный вывод по коду нахождения пары элементов списка в данном списке, сумма которого равна заданному целому числу

Question

Я пытался написать программу, которая проверяет, есть ли какие-либо два элемента в некотором списке L, сумма которых равна заданному целому числу S, и печатает эти два найденных элемента.Программа выдает сообщение об ошибке «! Ok», когда решение недоступно.

Ввод: в первой строке будет целое число T, представляющее количество тестовых случаев, за которыми следуют 2 строки ввода для каждогоконтрольный пример: в первой строке каждого контрольного примера будет 2 целых числа S и E, где S - ожидаемая сумма, а E - количество элементов в списке.Во второй строке будет E целых чисел, разделенных пробелом.Каждое целое число представляет элемент списка L. Элементы никак не сортируются, а некоторые могут иметь одинаковое значение.В случаях, когда число E равно 0, вторая строка будет пустой.

Все значения для элементов списка L будут находиться в том же диапазоне, что и значение S.

вывод: для каждого тестового случая вывод должен содержать следующие заданные значения: если имеетсяуникальное решение, два элемента x и y (из списка L) должны быть напечатаны, разделенные одним пробелом.Если существует несколько решений, будет напечатана только первая полная пара, которая появляется в списке и дает правильную сумму.Если решения не существует, должно быть напечатано сообщение об ошибке «! OK».

Ограничения и примечания:

1≤T≤1000

-10 ^ 6≤S≤10 ^ 6

0≤E≤2⋅10 ^ 4

Сумма значений E не более 10 ^ 7

Для выполнения этой задачи я попытался использовать хеш-таблицу, поскольку использование массивов может быть проблематичным вэтот случай, учитывая сложность времени выполнения.

Вот мой код:

#include <iostream>
#include <bits/stdc++.h>
#include <set>

using namespace std;

int main() 

{

    long long  int   numberElements=0, number;
    long long  int  sum=0, temp;
    unordered_set<long long int> s; 
    bool found=0;
    int numberCases;
    cin >> numberCases;

    for(int c = 1; c<=numberCases; c++)
    {
        s.clear();

        cin >> sum;

        found=0;
        cin>> numberElements;
        if(numberElements==0)
            cout << "!OK" <<endl;


        else
        {

        for(long long int  i = 0; i< numberElements && found==0; i++)
          {

            cin >> number;

           if (sum==(number+number))
             {
             if (s.find(number)!=s.end() )
              {
               cout<<number<<" "<<number<<endl;
               found=1;
              }
             }

           else
             {
               if(s.find(number)==s.end())
                 s.insert(number);

                 temp = sum - number; 

               if (s.find(temp)!=s.end())
               { cout<<temp<<" "<<number<<endl;
                 found=1; 
               }
             }  
         }
           if (found==0)
           cout << "!OK" <<endl;

      }
  }

    return 0;
}

Для следующего ввода:

6
8 4
1 2 4 4
8 4
1 2 7 9
8 4
1 2 8 9
8 4
4 5 3 4
8 4
4 1 1 8
8 4
-1 1 9 8

Ожидаемый результат:

4 4
1 7
!OK
3 5
!OK
-1 9

, тогда как на самом деле мой код выводит:

!OK
1 7
1 8
4 5
!OK
!OK

Я пытался обнаружить источник проблемы в моем коде, который вызывает нежелательный вывод, но пока мои усилия не возросли, нетуспех.
Любая помощь будет принята с благодарностью.

Answer 1

Мне только что удалось написать правильное решение проблемы.Вот мой код:

#include <iostream>
#include <bits/stdc++.h>
#include <set>
using namespace std;


int main()
{
long long  int   numberElements = 0, number;
long long  int  sum = 0, temp=0, element1=0, element2=0;
unordered_multiset<long long int> s;  
bool found = 0;
int numberCases;

cin >> numberCases;

for (int c = 1; c <= numberCases; c++)
{
    s.clear();

    cin >> sum;

    cin >> numberElements;
    if (numberElements == 0)
        cout << "!OK" << endl;


    else
    {
        found=0;

        for (long long int i = 0; i < numberElements; i++)
        {

            cin >> number;
            s.insert(number);
            if (found==0)
          {
              temp=sum-number;
              if(temp==number)
              {
                  if(s.count(temp)>1)
                  {
                      element1=number;
                      element2=number;
                      found=1;
                  }
              }

            else
              {
                  if(s.find(temp)!=s.end())
                    { 
                      element1=number;
                      element2=temp;
                      found=1;
                    }

              }
          }
        }


         if (found==1)   
            cout << min(element2,element1) << " " << max(element2, element1) << endl;
         else
            cout << "!OK" << endl;

      }

  }

   return 0;
}

Answer 2

я сделал несколько модификаций. Первым был создан unordered_multiset, это позволяет сохранять повторяющиеся значения (полезно проверить это sum = (number + number)). Основная проблема заключалась в том, что вы проверяли пустой список, поэтому проблема не нашла никакого значения для сравнения. Привет!

int main()
{

long long  int   numberElements = 0, number;
long long  int  sum = 0, temp;
unordered_multiset<long long int> s;  //Change set to multiset because multicase store repeated values, set don´t
bool found = 0;
bool RepeatedValue = false;
int numberCases;

cin >> numberCases;

for (int c = 1; c <= numberCases; c++)
{
    s.clear();

    cin >> sum;

    found = 0;
    cin >> numberElements;
    if (numberElements == 0)
        cout << "!OK" << endl;


    else
    {
        //This for is necesarry to charge the numbers before anlyze them. 
        //You were looking for a coincidence into a empty list

        for (long long int i = 0; i < numberElements; i++)
        {
            cin >> number;
            s.insert(number);
        }

        for (unordered_multiset<long long int>::iterator it = s.begin(); it != s.end() && found == 0;it++)
        {
            number = (*it);

            if (sum == (number + number))
            {
                //I addded this new conditional because I fill the list before analyze other number
                //In this case, use a find() is useless because always will a find a int of value "number"
                //count() returns the repeated times that a value was repeated

                if ( s.count(number) > 1)       
                {
                    cout << number << " " << number << endl;
                    found = 1;
                }
            }

            else
            {
                //This conditional is unnecessary, is find() returns s.end() 
                //means that not found the required number

                /*if (s.find(number) == s.end())
                    s.insert(number);*/

                temp = sum - number;

                if (s.find(temp) != s.end())
                {
                    cout << temp << " " << number << endl;
                    found = 1;
                }
            }
        }
        if (found == 0)
            cout << "!OK" << endl;

    }

}

return 0;

}