Определение первой комбинации из 2 чисел в массиве с суммой X

Question

Учитывая массив чисел и отдельное число, как бы вы определили первую комбинацию из 2 чисел в этом массиве, которая бы составляла это одно другое число?

Answer 1

Это решение использует дополнительную структуру данных для отслеживания разницы (ожидаемой пары) для каждого элемента в массиве.

for(int index=0; index<arr.size();index++) 
{
  if(expectedPair.contains(arr[index]))
  {
    pair = new Pair(expectedPair.get(arr[index]), index);
    break;
  }
  expectedPair.put(interestedNumber-arr[index],index); // TODO: handle case where duplicate numbers come up 
}
return pair;

Answer 2

for( i=0; i < ARRAY_SIZE; i++)
{
    if( arr[i] + arr[i+1] == x )
         return i;
}

Правильно, и если «первая комбинация» не означает «первая последовательная», то вам потребуется:

for( i=0; i < ARRAY_SIZE; i++ )
{
    for( j=i+1; j < ARRAY_SIZE; j++ )
    {
        if( arr[i] + arr[j] == x )
            return i, j;
    }
}

Обратите внимание, что это псевдокод.Поскольку вы не указали язык, вам придется самостоятельно обрабатывать типы и допустимые возвращаемые значения.

Answer 3

Если это очень большой массив, вы можете ускорить процесс поиска, отсортировав его и выполнив двоичный поиск. Примерно так:

for (i = 0; i < array_size; i++)
{
    if (binary_search(sorted_array, array_size, desired_value - array[i])
    {
        ...    
    }
}

Answer 4

Вы можете использовать

for (i = 0; i < array_size; ++i)
{
    for (j = i + 1; j < array_size; ++j)
    {
        if (array[i] + array[j] == desired_value)
        {
            // return these two numbers
        }
    }
}